Submission #51402

#	Time	Username	Problem	Language	Result	Execution time	Memory
51402		KieranHorgan	CATS (NOI14_cats)	C++17	4 / 25	1573 ms	329600 KiB

cats

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);

  int q;
  cin >> q;
  while(q--) {
    int X, L, N;
    cin >> X >> L >> N;
//    L = rand();
//    N = rand();
    string s;
    int storeX = X;
    int prevX = 0;
    while(1) {
      string t;
      for(X = prevX+1; X <= (s==""?1:prevX*2); X++) {
        int counter = X;
        vector<int> s1(10, 0), s2(10, 0);
        int xo = 0, x;
        while(counter) {
    //      cerr << counter << ":\t";
    //      for(int i = 10; i >= 1; i--)
    //        cerr << (s1[s1.size()-i]^xo) << " ";
    //      cerr << "\n\t";
    //      for(int i = 10; i >= 1; i--)
    //        cerr << s2[s2.size()-i] << " ";
    //      cerr << "\n";
          if(s1.empty()) s1.push_back(0);
          s2.push_back(s1.back() ^ xo);
          s1.pop_back();
          xo ^= 1;
          if(s2.back() > L) {
            counter--;
          } else {
            s2.back() = s2.back() + N*2;
            s1.push_back(s2.back()^xo);
            s1.push_back(s2.back()^xo);
            if(!s2.empty())
              s2.pop_back();
            if(!s2.empty())
              s2.pop_back();
          }
        }
        x = L/(2*N);
        x = (2*N)*(x+1);
        if(s2.back() == x) t.push_back('A');
        else if(s2.back() == x+1) t.push_back('B');
        else {
          cerr << "broke" << endl;
          return 0;
        }
      }
//      cerr << prevX+1 << " " << (s==""?1:prevX*2) << endl;
      prevX = (s==""?1:prevX*2);
      if(t == s) break;
      else s += t;
      if(s.size() > 1<<10) break;
    }
    int ad = 0;
    if(s.size() > 1<<10) ad = (__builtin_popcountll(storeX)+1)%2;
    else {
      storeX = (storeX-1)%s.size();
      ad = s[storeX]=='B';
    }
    int x = L/(2*N);
    x = (2*N)*(x+1);
    cout << x+ad << endl;
  }
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5