oj.uz

Submission #51355

# Submission time Handle Problem Language Result Execution time Memory
51355 2018-06-17T15:44:17 Z KieranHorgan CATS (NOI14_cats) C++17
4 / 25
 1500 ms 329788 KB 
#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<<15) break;
    }
    int ad = 0;
    if(s.size() > 1<<15) 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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 496 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1565 ms 804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 1112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 577 ms 329616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 600 ms 329788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -