oj.uz

Submission #101145

# Submission time Handle Problem Language Result Execution time Memory
101145 2019-03-17T06:01:05 Z square1001 Cake (CEOI14_cake) C++14
0 / 100
 292 ms 5712 KB 
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int inf = 1012345678;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, A, Q;
	cin >> N >> A; --A;
	vector<int> d(N);
	for (int i = 0; i < N; ++i) cin >> d[i];
	vector<int> L = { 1 }, R = { 1 };
	string first = "left";
	function<void(int)> set_first = [&](int pos) {
		if (pos == A) return;
		string last = (L.size() != R.size() ? (L.size() > R.size() ? "left" : "right") : (first == "left" ? "right" : "left"));
		if (pos < A) {
			bool erasure = false;
			while (!L.empty() && L.back() >= A - pos) L.pop_back(), erasure = true;
			if (!erasure && last == "left") return;
			L.push_back(A - pos);
			if (L.size() == 1) first = "right";
			while (R.size() > L.size() + (first == "right" ? 1 : 0)) R.pop_back();
		}
		if (pos > A) {
			bool erasure = false;
			while (!R.empty() && R.back() >= pos - A) R.pop_back(), erasure = true;
			if (!erasure && last == "left") return;
			R.push_back(pos - A);
			if (R.size() == 1) first = "left";
			while (L.size() > R.size() + (first == "left" ? 1 : 0)) L.pop_back();
		}
	};
	vector<int> ip(N);
	for (int i = 0; i < N; ++i) ip[d[i] - 1] = i;
	for (int i = 0; i < N; ++i) {
		set_first(ip[i]);
	}
	int S = min(N, 10);
	vector<int> first_ten(S);
	for (int i = N - 1; i >= N - S; --i) {
		first_ten[N - i - 1] = ip[i];
	}
	cin >> Q;
	for (int i = 0; i < Q; ++i) {
		string tp;
		cin >> tp;
		if (tp == "E") {
			int pos, e;
			cin >> pos >> e; --pos;
			int f = S - 1;
			for (int j = 0; j < S; ++j) {
				if (first_ten[j] == pos) {
					f = j;
				}
			}
			for (int j = f; j >= e; --j) {
				first_ten[j] = first_ten[j - 1];
			}
			first_ten[e - 1] = pos;
			for (int j = e - 1; j >= 0; --j) {
				set_first(first_ten[j]);
			}
		}
		if (tp == "F") {
			int pos;
			cin >> pos; --pos;
			int ans = 0;
			if (pos < A) {
				int ptr = lower_bound(L.begin(), L.end(), A - pos + 1) - L.begin() - 1;
				int rlim = (first == "left" ? ptr - 1 : ptr);
				ans = (A - pos) + (rlim + 1 == R.size() ? N - A : R[rlim + 1]) - 1;
			}
			if (pos > A) {
				int ptr = lower_bound(R.begin(), R.end(), pos - A + 1) - R.begin() - 1;
				int llim = (first == "right" ? ptr - 1 : ptr);
				ans = (pos - A) + (llim + 1 == L.size() ? A + 1 : L[llim + 1]) - 1;
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:75:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     ans = (A - pos) + (rlim + 1 == R.size() ? N - A : R[rlim + 1]) - 1;
                        ~~~~~~~~~^~~~~~~~~~~
cake.cpp:80:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     ans = (pos - A) + (llim + 1 == L.size() ? A + 1 : L[llim + 1]) - 1;
                        ~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 3140 KB Output isn't correct
2 Incorrect 193 ms 3236 KB Output isn't correct
3 Incorrect 170 ms 3144 KB Output isn't correct
4 Correct 153 ms 3164 KB Output is correct
5 Incorrect 245 ms 3556 KB Output isn't correct
6 Incorrect 292 ms 3400 KB Output isn't correct
7 Incorrect 196 ms 3656 KB Output isn't correct
8 Correct 178 ms 3548 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 1688 KB Output isn't correct
2 Incorrect 45 ms 1656 KB Output isn't correct
3 Incorrect 49 ms 1628 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 78 ms 2936 KB Output isn't correct
6 Incorrect 91 ms 3076 KB Output isn't correct
7 Incorrect 81 ms 2808 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 420 KB Output isn't correct
2 Incorrect 21 ms 512 KB Output isn't correct
3 Incorrect 47 ms 1352 KB Output isn't correct
4 Incorrect 57 ms 1272 KB Output isn't correct
5 Incorrect 61 ms 632 KB Output isn't correct
6 Incorrect 54 ms 2296 KB Output isn't correct
7 Incorrect 60 ms 1656 KB Output isn't correct
8 Incorrect 81 ms 2296 KB Output isn't correct
9 Incorrect 258 ms 5712 KB Output isn't correct
10 Incorrect 232 ms 2812 KB Output isn't correct
11 Incorrect 226 ms 4856 KB Output isn't correct
12 Incorrect 223 ms 5496 KB Output isn't correct
13 Incorrect 277 ms 5616 KB Output isn't correct