SHARE
TWEET

Untitled

a guest Sep 21st, 2019 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5. typedef pair<int, int> PII;
  6. typedef vector<int> VI;
  7. typedef vector<double> VD;
  8. #define MP make_pair
  9. #define PB push_back
  10. #define X first
  11. #define Y second
  12.  
  13. #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
  14. #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
  15. #define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  16. #define ALL(a) a.begin(), a.end()
  17. #define SZ(a) (int)((a).size())
  18. #define FILL(a, value) memset(a, value, sizeof(a))
  19. #define debug(a) cout << #a << " = " << a << endl;
  20.  
  21. const double PI = acos(-1.0);
  22. const LL INF = 1e9;
  23. const LL LINF = INF * INF;
  24. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  25. int dp[21][1 << 22];
  26. int was[61];
  27. int mask1 , mask2 , lenM1 , lenM2;
  28.  
  29. void findMasks(int len , int mask , int bit)
  30. {
  31.     mask2 = (mask >> (bit + 1));
  32.     mask1 = mask ^ (mask2 << (bit + 1));
  33.     mask2 <<= 1;
  34.     if((mask1 >> bit) & 1)
  35.         mask1 ^= (1 << bit);
  36.     lenM1 = bit - 1;
  37.     lenM2 = len - bit;
  38. }
  39. void updYe(int len , int mask , int bit)
  40. {
  41.     findMasks(len , mask , bit);
  42.     was[dp[lenM1][mask1] ^ dp[lenM2][mask2]] = 1;
  43.     was[dp[len][mask ^ (1 << bit)]] = 1;
  44. }
  45. void updNema(int len , int mask , int bit)
  46. {
  47.     if(bit == 1 && (mask & 1))
  48.         return;
  49.     if(bit == len && (mask & (1 << (len + 1))))
  50.         return;
  51.     findMasks(len , mask , bit);
  52.     mask2 |= 1;
  53.     mask1 |= (1 << (lenM1 + 1));
  54.     was[dp[lenM1][mask1] ^ dp[lenM2][mask2]] = 1;
  55. }
  56.  
  57.  
  58. #define ll long long
  59. #define ld long double
  60. #define vll vector <ll>
  61. #define vvll vector <vll>
  62. #define pll pair <ll, ll>
  63.  
  64. #define rep(i, a, b) for(ll i = a; i < b; i++)
  65. #define per(i, a, b) for(ll i = a - 1; i >= b; --i)
  66.  
  67. #define endl "\n"
  68. #define pb push_back
  69. #define pf push_front
  70.  
  71. #define all(v) (v).begin(), (v).end()
  72. #define rall(v) (v).rbegin(), (v).rend()
  73.  
  74. #define sorta(v) sort(all(v))
  75. #define sortd(v) sort(rall(v))
  76. #define vld vector<ld>
  77.  
  78. #define debug if (1)
  79. #define log(val) debug {cout << "\n" << #val << ": " << val << "\n";}
  80.  
  81. #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  82.  
  83. #define mod (ll)(1e9 + 7)
  84.  
  85. ostream & operator << (ostream & out, vll & a) {
  86.     for(auto i : a) out << i << " ";
  87.     return out;
  88. }
  89.  
  90. istream & operator >> (istream & in, vll & a) {
  91.     for(auto &i : a) in >> i;
  92.     return in;
  93. }
  94.  
  95. long long dp1[21][1 << 22];
  96. ll used[30];
  97. ll bits[22];
  98.  
  99. void precalc() {
  100.  
  101.     bits[0] = 1;
  102.     rep(i, 1, 22) {
  103.         bits[i] = (bits[i - 1] + 1) * 2 - 1;
  104.     }
  105.  
  106.     rep(n, 1, 21) {
  107.         per(mask, (1 << n), 0) {
  108.  
  109.             fill(used, used + 2 * n + 2, 0);
  110.  
  111.             rep(i, 0, n) {
  112.                 if((mask & (1 << i))) {
  113.                     ll x1 = 0, x2 = 0;
  114.                     if(i + 1 < n) {
  115.                         if(mask & (1 << (i + 1))) {
  116.                             x2 = (i + 2 < n ? dp1[n - i - 2][mask >> (i + 2)] : 0);
  117.                         } else {
  118.                             x2 = 1 ^ (i + 2 < n ? dp1[n - i - 2][mask >> (i + 2)] : 0);
  119.                         }
  120.                     }
  121.                     if(i - 1 >= 0) {
  122.                         if(mask & (1 << (i - 1))) {
  123.                             x1 = (i - 2 >= 0 ? dp1[i - 2 + 1][mask & bits[i - 2]] : 0);
  124.                         } else {
  125.                             x1 = 1 ^ (i - 2 >= 0 ? dp1[i - 2 + 1][mask & bits[i - 2]] : 0);
  126.                         }
  127.                     }
  128.  
  129.                     used[x1 ^ x2] = 1;
  130.                 } else {
  131.  
  132.                     used[dp1[n][mask ^ (1 << i)]] = 1;
  133.                     used[(i - 1 >= 0 ? dp1[i - 1 + 1][mask & bits[i - 1]] : 0) ^ (i + 1 < n ? dp1[n - i - 1][mask >> (i + 1)] : 0)] = 1;
  134.                 }
  135.             }
  136.             ll in = 0;
  137.             while(used[in])in++;
  138.             dp1[n][mask] = in;
  139.         }
  140.     }
  141.  
  142. }
  143.  
  144. ll solve(string & s) {
  145.  
  146.     ll ans = 0;
  147.     ll cur = 0;
  148.     ll cnt = 0;
  149.     ll n = s.size();
  150.     rep(i, 0, s.size()) {
  151.         if(s[i] == 'A') {
  152.             if(i - 1 >= 0) {
  153.                 if(s[i - 1] == 'B') {
  154.                     ans ^= dp1[cnt - 1][cur & bits[cnt - 1]];
  155.                 } else {
  156.                     assert(s[i - 1] == 'D');
  157.                     ans ^= (1 ^ dp1[cnt - 1][cur & bits[cnt - 1]]);
  158.                 }
  159.             }
  160.  
  161.             cnt = 0;
  162.             cur = 0;
  163.             if(i + 1 < n) {
  164.                 if(s[i + 1] == 'D') {
  165.                     ans ^= 1;
  166.                 }
  167.             }
  168.             i++;
  169.         } else if(s[i] == 'B') {
  170.             cur |= (1 << cnt);
  171.             cnt++;
  172.         } else if(s[i] == 'D') {
  173.             cnt++;
  174.         } else {
  175.             assert(0);
  176.         }
  177.     }
  178.  
  179.     if(cnt != 0) {
  180.         ans ^= dp1[cnt][cur];
  181.     }
  182.  
  183.     return ans;
  184. }
  185.  
  186. string getS(ll num) {
  187.     if(!num) return ".I.";
  188.     else if(num == 1) return (rand() % 2 == 0 ? "II." : ".II");
  189.     else if(num == 2) return "III";
  190.     else return "I.I";
  191.     /*
  192.     string s;
  193.     cin >> s;
  194.     return s;
  195.     */
  196. }
  197.  
  198. int main()
  199. {
  200.     //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  201.     //freopen("In.txt", "r", stdin);
  202.     //freopen("In.txt", "w", stdout);
  203.     for(int len = 1; len <= 20; len++)
  204.     {
  205.         for(int mask = 0; mask < (1 << (len + 2)); mask++)
  206.         {
  207.             memset(was , 0 , sizeof was);
  208.             for(int bit = 1; bit <= len; bit++)
  209.             {
  210.                 if((mask >> bit) & 1)
  211.                     updYe(len , mask , bit);
  212.                 else
  213.                     updNema(len , mask , bit);
  214.             }
  215.  
  216.             int ans = 0;
  217.             while(was[ans])
  218.                 ans++;
  219.             dp[len][mask] = ans;
  220.         }
  221.  
  222.     }
  223.  
  224.     precalc();
  225.     cout << "start : " << endl;
  226.     while(true) {
  227.         int n;
  228.         n = rand() % 3 + 1;
  229.         //cin >> n;
  230.         int mask = 0;
  231.         int len = 0;
  232.         int xrSum = 0;
  233.  
  234.         string cur = "";
  235.  
  236.         for(int i = 0; i < n; i++)
  237.         {
  238.             string s;
  239.             s = getS(rand() % 4);
  240.             int type;
  241.             if(s == ".I.") {
  242.                 type = 1;
  243.                 cur += "A";
  244.             }
  245.             else if (s == "II." || s == ".II") {
  246.                 type = 2;
  247.                 cur += "B";
  248.             }
  249.             else if (s == "III") {
  250.                 type = 3;
  251.                 cur += "D";
  252.             }
  253.             else {
  254.                 type = 4;
  255.             }
  256.             if(type == 1)
  257.             {
  258.                 mask |= (1 << (len + 1));
  259.                 xrSum ^= dp[len][mask];
  260.                 len = 0;
  261.                 mask = 1;
  262.             }
  263.             if(type == 4)
  264.             {
  265.                 xrSum ^= dp[len][mask];
  266.                 len = 0;
  267.                 mask = 0;
  268.             }
  269.             if(type == 3)
  270.             {
  271.                 len++;
  272.                 mask |= (1 << len);
  273.  
  274.             }
  275.             if(type == 2)
  276.                 len++;
  277.         }
  278.  
  279.         xrSum ^= dp[len][mask];
  280.         //cout << xrSum << endl;
  281.         //cout << solve(cur) << endl;
  282.         ll cur1 = xrSum, cur2 = solve(cur);
  283.         if(cur1 != cur2) {
  284.             cout << cur1 << ' ' << cur2 << " " << cur << endl;
  285.             return 0;
  286.         }
  287.     }
  288.  
  289.     //cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
  290.     return 0;
  291.  
  292. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top