oj.uz

Submission #124585

# Submission time Handle Problem Language Result Execution time Memory
124585 2019-07-03T14:33:54 Z NMAC427 CATS (NOI14_cats) C++17
8 / 25
 1500 ms 262148 KB 
// https://oj.uz/problem/view/NOI14_cats

#include <bits/stdc++.h>

#define int int64_t
#define coutV(x) for (const auto& e: x) {cerr << e << " ";} cerr << "\n"

using namespace std;


struct ZeroStack {
     vector<int> s;
     bool bitFlipState = false;

     void push(int v) {
          s.push_back(v ^ bitFlipState);
     }

     int top() {
          return (s.size() > 0 ? s.back() ^ bitFlipState : bitFlipState);
     }

     void pop() {
          if (!s.empty()) {
               s.pop_back();
          }
     }

     void flip() {
          bitFlipState = !bitFlipState;
     }

     void add() {
          int a = top(); pop();
          int b = top(); pop();
          push((a + b));
     }

     void print(int count) {
          for (int i = 1; i <= count; i++) {
               cerr << (s.size() >= i ? s[s.size() - i] ^ bitFlipState : bitFlipState) << " ";
          } cerr << "\n";
     }
};


int Q, X, L, N;

int simulate() {

     // COUNTER = X
     // WHILE COUNTER > 0
     //      S2 PUSH T1            //Push the top element of S1 onto S2
     //      S1 POP                //Pop the top element of S1
     //      FLIP LAST BINARY BIT OF ALL NUMBERS IN S1
     //      IF T2 > L
     //           COUNTER = COUNTER - 1
     //           IF COUNTER == 0 PRINT T2
     //      ELSE
     //           S2 PUSH N
     //           S2 PUSH N
     //           S2 ADD
     //           S2 ADD
     //           S1 PUSH T2
     //           S1 PUSH T2
     //           S2 POP
     //           S2 POP

     ZeroStack s1;
     ZeroStack s2;

     int counter = X;

     while (counter > 0) {
          s2.push(s1.top());
          s1.pop();
          s1.flip();

          if (s2.top() > L) {
               counter--;
               if (counter == 0) { return s2.top(); }
          } else {
               s2.push(N);
               s2.push(N);
               s2.add();
               s2.add();
               s1.push(s2.top());
               s1.push(s2.top());
               s2.pop();
               s2.pop();
          }

          // s1.print(4);
     }

     return -1;
}

int solve() {
     return simulate();
}

signed main() {
     cin >> Q;

     for (int _q = 0; _q < Q; _q++) {
          cin >> X >> L >> N;
          cout << solve() << "\n";
     }
}

Compilation message

cats.cpp: In member function 'void ZeroStack::print(int64_t)':
cats.cpp:41:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                cerr << (s.size() >= i ? s[s.size() - i] ^ bitFlipState : bitFlipState) << " ";
                         ~~~~~~~~~^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 760 KB Output is correct
2 Correct 26 ms 4580 KB Output is correct
3 Correct 24 ms 2540 KB Output is correct
4 Correct 18 ms 1520 KB Output is correct
5 Correct 22 ms 4580 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1149 ms 7964 KB Output is correct
2 Correct 772 ms 8388 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 7008 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 1580 ms 4476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 977 ms 262148 KB Execution killed with signal 9 (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 956 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -