Advertisement
ivnikkk

Untitled

Jan 11th, 2022
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1. #pragma GCC optimize("03")
  2. #pragma GCC optimize("Ofast")
  3. #define _CRT_SECURE_NO_WARNINGS
  4. #include <iostream>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <iomanip>
  9. #include <fstream>
  10. #include <string>
  11. #include <set>
  12. #include <deque>
  13. #include <queue>
  14. #include <map>
  15. #include <bitset>
  16. #include <random>
  17. #include <cassert>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20. #include <math.h>
  21. #include <cstdlib>
  22. using namespace std;
  23. #define all(a)            a.begin(), a.end()
  24. typedef long long ll;
  25. typedef long double ld;
  26.  
  27. double temp;
  28. double t0 = 1000;
  29.  
  30. double gen_rand()
  31. {
  32.     int x = rand() + 1, y = rand() + 1;
  33.     x %= y;
  34.     return x / (double)y;
  35. }
  36. pair<ll, string> get(vector<ll>& a,vector<ll> &check) {
  37.     ll itl = 0, itr = (ll)a.size() - 1;
  38.     string sub = "";
  39.     ll cnt0 = 0, cnt1 = 0;
  40.     for (ll i = 0; i < (ll)check.size(); i++) {
  41.         if (check[i]) {
  42.             while (cnt1 > itr) {
  43.                 itr--;
  44.                 sub += 'l';
  45.             }
  46.             while (cnt1 > itl) {
  47.                 itl++;
  48.                 sub += 'R';
  49.             }
  50.             cnt1++;
  51.         }
  52.         else {
  53.             ll lol = (ll)a.size() - cnt0 - 1;
  54.             while (lol < itl) {
  55.                 itl--;
  56.                 sub += 'L';
  57.             }
  58.             while (lol < itr) {
  59.                 itr--;
  60.                 sub += 'r';
  61.             }
  62.             cnt0++;
  63.         }
  64.     }
  65.     return { (ll)sub.size(),sub };
  66. }
  67. signed main() {
  68. //#ifdef _DEBUG
  69.   //  freopen("input.txt", "r", stdin);
  70.     //freopen("output.txt", "w", stdout);
  71. //#endif
  72.     ios_base::sync_with_stdio(false);
  73.     cin.tie(nullptr);
  74.     srand(time(nullptr));
  75.     ll n;
  76.     cin >> n;
  77.     vector<ll> a(n);
  78.     for (ll i = 0; i < n; i++) {      
  79.         cin >> a[i];
  80.     }
  81.     vector<ll> prev(2 * n);
  82.     for (ll i = 0; i < 2*n; i++) {
  83.         prev[i] = (i < n);
  84.     }
  85.     //shuffle(all(prev), rand());
  86.     string ans = "#";
  87.     ll time = 0;
  88.     ll best_len = INT_MAX;
  89.     while (true) {
  90.         if (clock() / (double)CLOCKS_PER_SEC >= 0.9){
  91.             cout << ans << endl;
  92.             return 0;
  93.         }
  94.         pair<ll, string> last_val = get(a, prev);
  95.         if (last_val.first < best_len) {
  96.             ans = last_val.second;
  97.             best_len = last_val.first;
  98.         }
  99.         vector<ll> is_best = prev;
  100.         for (ll i = 0; i < n * temp / t0; i++){
  101.             swap(is_best[rand() % (2*n)], is_best[rand() % (2*n)]);
  102.         }
  103.         pair<ll,string>now = get(a, is_best);
  104.         if (now.first < best_len) {
  105.             ans = now.second;
  106.             best_len = now.first;
  107.         }
  108.         double ok = exp(-(now.first - last_val.first) / temp);
  109.         if (now.first < last_val.first || gen_rand() <= ok) {
  110.             prev = is_best;
  111.         }
  112.         temp *= 0.999995;
  113.     }
  114.     cout << ans << endl;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement