#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;
const int maxN = 2e5 + 20;
int a[maxN * 2];
pair<int, int> memo[maxN];
int N, R, K;
int get_color(int X) {
if (X > K) {
return WHITE;
}
else if (X < K) {
return BLACK;
}
else {
return GRAY;
}
}
namespace sub1 {
int cnt[maxN * 4][3];
int sum[3];
pair<int, int> simulate(int start) {
for (int i = 0; i < maxN * 4; i++) {
for (int j = 0; j < 3; j++) {
cnt[i][j] = 0;
}
}
for (int i = 0; i < 3; i++) {
sum[i] = 0;
}
int color1 = -1;
int color2 = -1;
for (int i = 1; i <= start * 2 - 1; i++) {
int color = get_color(a[i]);
int pos = (i + 1) / 2;
if (pos == 1) {
if (color1 == -1) {
color1 = color;
}
else {
color2 = color;
}
}
else {
cnt[pos][color]++;
}
}
if (start == 1) {
if (color1 == -1) {
color1 = GRAY;
}
else {
color2 = GRAY;
}
}
else {
cnt[start][GRAY]++;
}
for (int i = start * 2; i <= N * 2 - 1; i++) {
int color = get_color(a[i]);
int pos = i / 2 + 1;
if (pos == 1) {
if (color1 == -1) {
color1 = color;
}
else {
color2 = color;
}
}
else {
cnt[pos][color]++;
}
}
int first_gray = -1;
int wraps = 0;
for (int round = 1; round <= N * 3; round++) {
if (round > N * 2 && (color1 == GRAY || color2 == GRAY)) {
first_gray = round - 1;
break;
}
if (color1 < color2) {
swap(color1, color2);
}
if (color2 == GRAY) {
wraps++;
}
cnt[round + N][color2]++;
for (int i = 0; i < 3; i++) {
sum[i] += cnt[round + 1][i];
}
for (int i = 2; i >= 0; i--) {
if (sum[i] > 0) {
color2 = i;
sum[i]--;
break;
}
}
}
if (R > first_gray) {
wraps++;
}
int pos = (first_gray + N - R) % N + 1;
return make_pair(pos, wraps);
}
}
namespace sub2 {
pair<int, int> simulate(int start) {
assert(false);
return make_pair(-1, -1);
}
}
pair<int, int> get_final(int start) {
if (memo[start].first != -1) {
return memo[start];
}
if (K <= N + 1) {
return (memo[start] = sub1::simulate(start));
}
else {
return (memo[start] = sub2::simulate(start));
}
}
pair<int, int> solve(int lt, int rt) {
pair<int, int> res = make_pair(N + 1, -1);
for (int i = rt; i >= lt; i--) {
auto final = get_final(i);
if (final.first < res.first) {
res = make_pair(final.first, i);
}
}
return res;
}
void just_do_it() {
cin >> N >> R >> K;
R = N * 2 + R % N;
for (int i = 1; i <= N * 2 - 1; i++) {
cin >> a[i];
}
if (N == 1) {
cout << 1;
return;
}
if (K == 1) {
cout << N;
return;
}
if (K == N * 2) {
cout << 2;
return;
}
for (int i = 1; i <= N; i++) {
memo[i] = make_pair(-1, -1);
}
auto res = solve(1, N);
cout << res.second;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
138 ms |
9712 KB |
Output is correct |
| 4 |
Execution timed out |
2070 ms |
9684 KB |
Time limit exceeded |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
9672 KB |
Output is correct |
| 2 |
Correct |
228 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
1510 ms |
9752 KB |
Output is correct |
| 4 |
Execution timed out |
2069 ms |
10056 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2060 ms |
14536 KB |
Time limit exceeded |
| 6 |
Correct |
259 ms |
9712 KB |
Output is correct |
| 7 |
Correct |
1091 ms |
9736 KB |
Output is correct |
| 8 |
Execution timed out |
2069 ms |
10068 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2055 ms |
10204 KB |
Time limit exceeded |
| 10 |
Correct |
1269 ms |
9748 KB |
Output is correct |
| 11 |
Execution timed out |
2068 ms |
10196 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2071 ms |
9684 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2085 ms |
13100 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2066 ms |
9812 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2071 ms |
10548 KB |
Time limit exceeded |
| 16 |
Correct |
264 ms |
9716 KB |
Output is correct |
| 17 |
Correct |
1491 ms |
9752 KB |
Output is correct |
| 18 |
Execution timed out |
2047 ms |
9684 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2076 ms |
9812 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2073 ms |
9744 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2074 ms |
10196 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2069 ms |
10440 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2055 ms |
14868 KB |
Time limit exceeded |
| 24 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 25 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 26 |
Runtime error |
3 ms |
728 KB |
Execution killed with signal 6 |
| 27 |
Runtime error |
5 ms |
1364 KB |
Execution killed with signal 6 |
| 28 |
Runtime error |
25 ms |
6088 KB |
Execution killed with signal 6 |
| 29 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 30 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 31 |
Runtime error |
4 ms |
1364 KB |
Execution killed with signal 6 |
| 32 |
Runtime error |
37 ms |
8280 KB |
Execution killed with signal 6 |
| 33 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 34 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 35 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 36 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 37 |
Runtime error |
4 ms |
1248 KB |
Execution killed with signal 6 |
| 38 |
Runtime error |
6 ms |
1492 KB |
Execution killed with signal 6 |
| 39 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 40 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 41 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 42 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 6 |
| 43 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 44 |
Runtime error |
3 ms |
980 KB |
Execution killed with signal 6 |
| 45 |
Runtime error |
7 ms |
1412 KB |
Execution killed with signal 6 |
| 46 |
Runtime error |
5 ms |
1488 KB |
Execution killed with signal 6 |
| 47 |
Runtime error |
35 ms |
9420 KB |
Execution killed with signal 6 |
