#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 200000 + 7;
int n;
int r;
int my_rank;
int init_ord[N];
int ord[N];
int winner[N];
int loser[N];
vector<int> guys[N];
bool wannap;
void simulate_step_for_get_brute() {
for (int i = 0; i < n; i++) {
if (ord[2 * i] < ord[2 * i + 1]) {
winner[i] = ord[2 * i];
loser[i] = ord[2 * i + 1];
} else {
winner[i] = ord[2 * i + 1];
loser[i] = ord[2 * i];
}
guys[i].clear();
}
guys[0].push_back(winner[0]);
for (int i = 1; i < n; i++) {
guys[i - 1].push_back(winner[i]);
guys[i].push_back(loser[i]);
}
guys[n - 1].push_back(loser[0]);
for (int i = 0; i < n; i++) {
assert((int) guys[i].size() == 2);
for (int it = 0; it < 2; it++) {
ord[2 * i + it] = guys[i][it];
}
}
}
void print() {
cout << " ----> ";
for (int i = 0; i < 2 * n; i++) {
cout << ord[i] + 1 << " ";
}
cout << "\n";
}
int get_brute(int pos) {
int sol = -1;
assert(0 <= pos && pos < 2 * n);
ord[pos] = my_rank;
for (int i = 0; i < pos; i++) {
ord[i] = init_ord[i];
}
for (int i = pos + 1; i < 2 * n; i++) {
ord[i] = init_ord[i - 1];
}
if (wannap) print();
for (int j = 1; j <= r; j++) {
simulate_step_for_get_brute();
if (wannap) print();
}
for (int i = 0; i < 2 * n; i++) {
if (ord[i] == my_rank) {
sol = i;
}
}
if (wannap) cout << "= " << sol << "\n";
assert(sol != -1);
return sol / 2;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
///freopen ("input", "r", stdin);
wannap = 0;
cin >> n >> r;
r = 2 * n + r % n;
cin >> my_rank;
my_rank--;
for (int i = 0; i < 2 * n - 1; i++) {
cin >> init_ord[i];
init_ord[i]--;
}
// get_brute(0);
//exit(0);
int mn = (int) 1e9, best = -1;
for (int i = n - 1; i >= 0; i--) {
int x = get_brute(2 * i);
if (x < mn) {
mn = x;
best = i;
}
}
cout << best + 1 << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9696 KB |
Output is correct |
| 2 |
Execution timed out |
2078 ms |
9732 KB |
Time limit exceeded |
| 3 |
Correct |
26 ms |
9724 KB |
Output is correct |
| 4 |
Execution timed out |
2072 ms |
9804 KB |
Time limit exceeded |
| 5 |
Correct |
5 ms |
9704 KB |
Output is correct |
| 6 |
Correct |
131 ms |
9728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9708 KB |
Output is correct |
| 2 |
Correct |
176 ms |
9732 KB |
Output is correct |
| 3 |
Execution timed out |
2064 ms |
9804 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2041 ms |
10612 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2025 ms |
21200 KB |
Time limit exceeded |
| 6 |
Correct |
138 ms |
9724 KB |
Output is correct |
| 7 |
Execution timed out |
2059 ms |
9676 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2013 ms |
10620 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2102 ms |
10992 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2085 ms |
9724 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2028 ms |
11100 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2065 ms |
9860 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2013 ms |
17968 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2066 ms |
9932 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2058 ms |
11756 KB |
Time limit exceeded |
| 16 |
Correct |
162 ms |
9676 KB |
Output is correct |
| 17 |
Execution timed out |
2064 ms |
9804 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2103 ms |
9744 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2079 ms |
9932 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2045 ms |
9924 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2072 ms |
11064 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2082 ms |
11724 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2037 ms |
21876 KB |
Time limit exceeded |
| 24 |
Correct |
168 ms |
9724 KB |
Output is correct |
| 25 |
Execution timed out |
2077 ms |
9804 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2066 ms |
10000 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2077 ms |
11084 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2099 ms |
18280 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2081 ms |
9804 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2056 ms |
9924 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2057 ms |
11000 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2019 ms |
21472 KB |
Time limit exceeded |
| 33 |
Correct |
163 ms |
9676 KB |
Output is correct |
| 34 |
Correct |
143 ms |
9916 KB |
Output is correct |
| 35 |
Execution timed out |
2053 ms |
9932 KB |
Time limit exceeded |
| 36 |
Execution timed out |
2086 ms |
9804 KB |
Time limit exceeded |
| 37 |
Execution timed out |
2069 ms |
10884 KB |
Time limit exceeded |
| 38 |
Execution timed out |
2062 ms |
11304 KB |
Time limit exceeded |
| 39 |
Correct |
139 ms |
9732 KB |
Output is correct |
| 40 |
Execution timed out |
2084 ms |
9676 KB |
Time limit exceeded |
| 41 |
Execution timed out |
2083 ms |
9860 KB |
Time limit exceeded |
| 42 |
Execution timed out |
2045 ms |
9852 KB |
Time limit exceeded |
| 43 |
Execution timed out |
2073 ms |
10060 KB |
Time limit exceeded |
| 44 |
Execution timed out |
2058 ms |
10344 KB |
Time limit exceeded |
| 45 |
Execution timed out |
2077 ms |
11008 KB |
Time limit exceeded |
| 46 |
Execution timed out |
2057 ms |
11128 KB |
Time limit exceeded |
| 47 |
Execution timed out |
2082 ms |
23236 KB |
Time limit exceeded |
