Advertisement
ivnikkk

Untitled

Jan 11th, 2022
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.14 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. #include <chrono>
  23. using namespace std;
  24. using namespace std::chrono;
  25. #define all(a)            a.begin(), a.end()
  26. typedef long long ll;
  27. typedef long double ld;
  28. ll time1 = 0;
  29. double temp;
  30. double t0 = 1000;
  31. double rnd() { return double(rand()) / RAND_MAX; }
  32. pair<ll, string> get(vector<ll>& a,vector<ll> &check) {
  33.     ll itl = 0, itr = (ll)a.size() - 1;
  34.     string sub = "";
  35.     ll cnt0 = 0, cnt1 = 0;
  36.     for (ll i = 0; i < (ll)check.size(); i++) {
  37.         if (check[i]) {
  38.             while (cnt1 > itr) {
  39.                 itr--;
  40.                 sub += 'l';
  41.             }
  42.             while (cnt1 > itl) {
  43.                 itl++;
  44.                 sub += 'R';
  45.             }
  46.             cnt1++;
  47.         }
  48.         else {
  49.             ll lol = (ll)a.size() - cnt0 - 1;
  50.             while (lol < itl) {
  51.                 itl--;
  52.                 sub += 'L';
  53.                 time1++;
  54.             }
  55.             while (lol < itr) {
  56.                 itr--;
  57.                 sub += 'r';
  58.             }
  59.             cnt0++;
  60.         }
  61.     }
  62.     return { (ll)sub.size(),sub };
  63. }
  64. signed main() {
  65. //#ifdef _DEBUG
  66.   //  freopen("input.txt", "r", stdin);
  67.     //freopen("output.txt", "w", stdout);
  68. //#endif
  69.     ios_base::sync_with_stdio(false);
  70.     cin.tie(nullptr);
  71.     srand(time(nullptr));
  72.     ll n;
  73.     high_resolution_clock::time_point t1 = high_resolution_clock::now();
  74.     cin >> n;
  75.     vector<ll> a(n);
  76.     for (ll i = 0; i < n; i++) {      
  77.         cin >> a[i];
  78.     }
  79.     vector<ll> prev(2 * n);
  80.     for (ll i = 0; i < 2*n; i++) {
  81.         prev[i] = (i < n);
  82.     }
  83.     //shuffle(all(prev), rand());
  84.     string ans = "";
  85.     //ll count=0;
  86.     ll best_len = INT_MAX;
  87.     ll cnt = 0;
  88.     while (true) {
  89.         high_resolution_clock::time_point t2 = high_resolution_clock::now();
  90.         duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
  91.         double sup = time_span.count();
  92.         if (sup >= 1.8) {
  93.             cout << ans ;
  94.             break;
  95.         }
  96.         cnt++;
  97.         pair<ll, string> last_val = get(a, prev);
  98.         if (last_val.first < best_len) {
  99.             ans = last_val.second;
  100.             best_len = last_val.first;
  101.         }
  102.         vector<ll> is_best = prev;
  103.         for (ll i = 0; i < n * temp / t0; i++){
  104.             swap(is_best[rand() % (2*n)], is_best[rand() % (2*n)]);
  105.         }
  106.         pair<ll,string>now = get(a, is_best);
  107.         if (now.first < best_len) {
  108.             ans = now.second;
  109.             best_len = now.first;
  110.         }
  111.         double go = exp((now.first - last_val.first) / temp);
  112.         if (now.first < last_val.first || rnd() <= go) {
  113.             prev = is_best;
  114.         }
  115.         temp *= 0.999995;
  116.     }
  117.     if (!cnt)return 132;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement