oj.uz

Submission #124629

# Submission time Handle Problem Language Result Execution time Memory
124629 2019-07-03T15:42:45 Z NMAC427 CATS (NOI14_cats) C++17
8 / 25
 1500 ms 504 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 << setw(2) << (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();
		}

		#ifndef __APPLE__
		cerr << "Counter: " << counter << "\n";
		cerr << "S1: ";
		s1.print(8);
		cerr << "S2: ";
		s2.print(8);
		cerr << "\n";
		#endif
	}

	return -1;
}

int nI(int i) {
	int k = 1;

	for (int j = 0; j < i; j++) {
		k = 2 * k + 1;
	}

	return k;
}

int simulate_() {

	ZeroStack s1;
	int s2Top = 0;

	int nii = nI((L / (2 * N)) + 1) + 1;
	// cerr << nii << "\n";

	int counter = (X % nii) + nii;


	while (counter > 0) {
		s2Top = s1.top();
		s1.pop();
		s1.flip();

		if (s2Top > L) {
			// cerr << "X";

			// if (counter == 5) {
			// 	s1.print(X + 1);
			// }

			// cerr << s2Top << " s2t\n";

			counter--;
			if (counter == 0) { return s2Top; }
		} else {
			// cerr << " ";
			s2Top += 2 * N;
			s1.push(s2Top);
			s1.push(s2Top);
		}
	}

	return -1;
}

int solve() {
	// int s = simulate();
	int s_ = simulate_();

	// cerr << s << " " << s_ << "\n";
	// assert(s == s_);

	return s_;
}

signed main() {
	cin >> Q;

	// for (int _q = 0; _q < Q; _q++) {
	// 	cin >> X >> L >> N;
		
	// 	for (X = 1; X < 64; X++) {
	// 		cerr << X << " -> ";
	// 		solve();
	// 	}
	// }

	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:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    cerr << setw(2) << (s.size() >= i ? s[s.size() - i] ^ bitFlipState : bitFlipState) << " ";
                        ~~~~~~~~~^~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 504 KB Execution killed with signal 8 (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 Execution timed out 1563 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -