hpnq

Untitled

Jan 18th, 2023
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. //---H---
  2. #include "bits/stdc++.h"
  3. //#include <windows.h>
  4. //speed coding
  5.  
  6. #define mp make_pair
  7. #define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " ";  }cout << "\n";} ;
  8. #define f first
  9. #define s second
  10. #define loop(i, x, n) for (ll i = x; i < n; i++)
  11. #define joop(x, n) for (ll j = x; j < n; j++)
  12. #define lp(n) for (ll i = 0; i < n; i++)
  13. #define err cout << "ERROR" << endl;
  14. #define all(x) x.begin(), x.end()
  15. #define pb push_back
  16. #define sz(x) x.size()
  17. #define rndm rng()
  18.  
  19. // types
  20. #define pii pair<int, int>
  21. #define pll pair<ll, ll>
  22. #define vvi vector<vector<int>>
  23. #define vvll vector<vector<ll>>
  24. typedef long long ll;
  25. typedef long double ld;
  26.  
  27. // types of data
  28. #define inf 1000000000
  29. #define infll 1000000000000000000
  30. #define INF ll(1e18)
  31.  
  32. //#define md 998244353
  33. #define mod 1000000009
  34. #define K 239017
  35.  
  36. //#define DEBUG 1
  37. using namespace std;
  38. mt19937_64 rng(228228);
  39. uniform_int_distribution<ll> drist;
  40. int n, m, k;
  41.  
  42. string s;
  43.  
  44.  
  45. int check(string &cp, int a, int b){
  46.     int cnt = 0;
  47.     cnt -= s[a] == cp[a];
  48.     cnt -= s[b] == cp[b];
  49.     cnt += s[a] == cp[b];
  50.     cnt += s[b] == cp[a];
  51.     if(s[a] == cp[a]){
  52.  
  53.     }
  54.     return cnt;
  55. }
  56.  
  57.  
  58. ld p(ld dx, ld t){
  59.     return exp(dx/t);
  60. }
  61.  
  62. void solve() {
  63.     cin >> s;
  64.     n = sz(s);
  65.     string cp = s;
  66.     int ans = n;
  67.     ld t = 1;
  68.     ld mt = 0.99999;
  69.     while(ans && clock()/1.0*(CLOCKS_PER_SEC) < 5){
  70.         int a = rand() % n;
  71.         int b = rand() % n;
  72.         ld dx = check(cp, a, b);
  73.         if(dx < 0 or p(dx, t) > (ld)(rand()%infll)/infll){
  74.             swap(cp[a], cp[b]);
  75.             ans+= (int)dx;
  76.         }
  77.         t*=mt;
  78.     }
  79.  
  80.     cout << s << "\n" <<  cp;
  81.  
  82. }
  83.  
  84. int main() {
  85. //    setlocale(LC_ALL, "Russian");
  86. //    SetConsoleOutputCP(1251);
  87.     ios::sync_with_stdio(0);
  88.     cin.tie(0);
  89. #ifdef DEBUG
  90.     freopen("text.txt", "r", stdin);
  91. #else
  92. #endif
  93. //    ll ggwp;
  94. //    cin >> ggwp;
  95. //    loop(xuy, 0, ggwp){
  96. //        solve();
  97. //    }
  98.     solve();
  99.     return 0;
  100. }
Add Comment
Please, Sign In to add comment