oj.uz

Submission #124641

# Submission time Handle Problem Language Result Execution time Memory
124641 2019-07-03T16:04:49 Z NMAC427 CATS (NOI14_cats) C++17
12 / 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 calculateFlips(int i, int factor) {

	int nii = nI(factor) + 1;
	i = min(i, (i % nii) + nii);



}

int simulate_() {

	ZeroStack s1;
	int s2Top = 0;

	int f   = (L / (2 * N)) + 1;
	int nii = nI(f) + 1;

	int baseAns = 2 * f * N;
	int patternLength = 1 << f;

	// cerr << nii << "\n";

	int counter = (X % nii); //min(X, (X % nii) + nii);

	if (counter == 0) {
		counter = nii;
	}


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

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

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

	return -1;
}

int solve() {
	#ifdef __APPLE__
	int s = simulate();
	int s_ = simulate_();

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

	return s;
	#else

	return simulate_();

	#endif
}

signed main() {
	cin >> Q;

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

	#else

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

	#endif
}

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) << " ";
                        ~~~~~~~~~^~~~
cats.cpp: In function 'int64_t calculateFlips(int64_t, int64_t)':
cats.cpp:123:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
cats.cpp: In function 'int64_t simulate_()':
cats.cpp:133:6: warning: unused variable 'baseAns' [-Wunused-variable]
  int baseAns = 2 * f * N;
      ^~~~~~~
cats.cpp:134:6: warning: unused variable 'patternLength' [-Wunused-variable]
  int patternLength = 1 << f;
      ^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 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 3 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
4.0 / 4.0

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

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 1537 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -