Submission #124585

#	Time	Username	Problem	Language	Result	Execution time	Memory
124585		NMAC427	CATS (NOI14_cats)	C++17	8 / 25	1580 ms	262148 KiB

cats

// 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 (stderr)

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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5