# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
44718 |
2018-04-05T12:26:19 Z |
cheater2k |
Swap (BOI16_swap) |
C++14 |
|
127 ms |
35288 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int MAX = 1500005;
const int INF = 1e9;
typedef pair<int, int> ii;
int n, a[N], id;
int at[MAX];
int best[MAX];
map <int, int> mp[N];
int dp(int v, int val) {
if (val == INF) return v; // empty vector
if (mp[v].find(val) != mp[v].end()) {
return at[mp[v][val]];
}
mp[v][val] = ++id;
int curid = id;
int l = (v * 2 <= n) ? a[v * 2] : INF;
int r = (v * 2 + 1 <= n) ? a[v * 2 + 1] : INF;
int w[3] = {val, l, r};
if (w[0] < min(w[1], w[2])) {
dp(v << 1, w[1]);
dp(v << 1 | 1, w[2]);
return at[curid] = v;
}
else if (w[1] < min(w[0], w[2])) {
dp(v << 1 | 1, w[2]);
return at[curid] = dp(v << 1, w[0]);
}
else {
// -> w[2], w[0], w[1]
// -> w[2], w[1], w[0]
if (w[0] < w[1]) {
int p = dp(v << 1, w[0]);
int q = dp(v << 1 | 1, w[0]);
best[curid] = p < q ? 0 : 1;
//cerr << v << ' ' << val << " -> best = " << best[curid] << endl;
if (p < q) dp(v << 1 | 1, w[1]);
else dp(v << 1, w[1]);
return at[curid] = min(p, q);
}
int p = dp(v << 1, w[1]);
int q = dp(v << 1 | 1, w[1]);
if (p < q) {
best[curid] = 1;
//cerr << v << ' ' << val << " -> best = " << 1 << endl;
return at[curid] = dp(v << 1 | 1, w[0]);
} else {
best[curid] = 0;
//cerr << v << ' ' << val << " -> best = " << 0 << endl;
return at[curid] = dp(v << 1, w[0]);
}
}
}
void trace(int v, int val) {
if (val == INF) return;
int l = (v * 2 <= n) ? a[v * 2] : INF;
int r = (v * 2 + 1 <= n) ? a[v * 2 + 1] : INF;
int w[3] = {val, l, r};
if (w[0] < min(w[1], w[2])) {
a[v] = w[0];
trace(v << 1, w[1]);
trace(v << 1 | 1, w[2]);
}
else if (w[1] < min(w[0], w[2])) {
a[v] = w[1];
trace(v << 1, w[0]);
trace(v << 1 | 1, w[2]);
}
else {
a[v] = w[2];
int curid = mp[v][val];
trace(v << 1, w[best[curid]]);
trace(v << 1 | 1, w[best[curid] ^ 1]);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
dp(1, a[1]);
trace(1, a[1]);
for (int i = 1; i <= n; ++i) {
printf("%d ", a[i]);
}
printf("\n");
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
swap.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i);
~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
9 ms |
9888 KB |
Output is correct |
4 |
Correct |
11 ms |
9896 KB |
Output is correct |
5 |
Correct |
9 ms |
9896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
9 ms |
9888 KB |
Output is correct |
4 |
Correct |
11 ms |
9896 KB |
Output is correct |
5 |
Correct |
9 ms |
9896 KB |
Output is correct |
6 |
Correct |
9 ms |
9896 KB |
Output is correct |
7 |
Correct |
9 ms |
9896 KB |
Output is correct |
8 |
Correct |
11 ms |
9948 KB |
Output is correct |
9 |
Correct |
9 ms |
9948 KB |
Output is correct |
10 |
Correct |
9 ms |
9948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
9 ms |
9888 KB |
Output is correct |
4 |
Correct |
11 ms |
9896 KB |
Output is correct |
5 |
Correct |
9 ms |
9896 KB |
Output is correct |
6 |
Correct |
9 ms |
9896 KB |
Output is correct |
7 |
Correct |
9 ms |
9896 KB |
Output is correct |
8 |
Correct |
11 ms |
9948 KB |
Output is correct |
9 |
Correct |
9 ms |
9948 KB |
Output is correct |
10 |
Correct |
9 ms |
9948 KB |
Output is correct |
11 |
Correct |
9 ms |
10068 KB |
Output is correct |
12 |
Correct |
12 ms |
10068 KB |
Output is correct |
13 |
Correct |
12 ms |
10196 KB |
Output is correct |
14 |
Correct |
13 ms |
10196 KB |
Output is correct |
15 |
Correct |
11 ms |
10196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
9 ms |
9888 KB |
Output is correct |
4 |
Correct |
11 ms |
9896 KB |
Output is correct |
5 |
Correct |
9 ms |
9896 KB |
Output is correct |
6 |
Correct |
9 ms |
9896 KB |
Output is correct |
7 |
Correct |
9 ms |
9896 KB |
Output is correct |
8 |
Correct |
11 ms |
9948 KB |
Output is correct |
9 |
Correct |
9 ms |
9948 KB |
Output is correct |
10 |
Correct |
9 ms |
9948 KB |
Output is correct |
11 |
Correct |
9 ms |
10068 KB |
Output is correct |
12 |
Correct |
12 ms |
10068 KB |
Output is correct |
13 |
Correct |
12 ms |
10196 KB |
Output is correct |
14 |
Correct |
13 ms |
10196 KB |
Output is correct |
15 |
Correct |
11 ms |
10196 KB |
Output is correct |
16 |
Correct |
34 ms |
14572 KB |
Output is correct |
17 |
Correct |
36 ms |
14572 KB |
Output is correct |
18 |
Correct |
36 ms |
14604 KB |
Output is correct |
19 |
Correct |
49 ms |
15888 KB |
Output is correct |
20 |
Correct |
35 ms |
15900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
9 ms |
9888 KB |
Output is correct |
4 |
Correct |
11 ms |
9896 KB |
Output is correct |
5 |
Correct |
9 ms |
9896 KB |
Output is correct |
6 |
Correct |
9 ms |
9896 KB |
Output is correct |
7 |
Correct |
9 ms |
9896 KB |
Output is correct |
8 |
Correct |
11 ms |
9948 KB |
Output is correct |
9 |
Correct |
9 ms |
9948 KB |
Output is correct |
10 |
Correct |
9 ms |
9948 KB |
Output is correct |
11 |
Correct |
9 ms |
10068 KB |
Output is correct |
12 |
Correct |
12 ms |
10068 KB |
Output is correct |
13 |
Correct |
12 ms |
10196 KB |
Output is correct |
14 |
Correct |
13 ms |
10196 KB |
Output is correct |
15 |
Correct |
11 ms |
10196 KB |
Output is correct |
16 |
Correct |
34 ms |
14572 KB |
Output is correct |
17 |
Correct |
36 ms |
14572 KB |
Output is correct |
18 |
Correct |
36 ms |
14604 KB |
Output is correct |
19 |
Correct |
49 ms |
15888 KB |
Output is correct |
20 |
Correct |
35 ms |
15900 KB |
Output is correct |
21 |
Correct |
125 ms |
28576 KB |
Output is correct |
22 |
Correct |
123 ms |
28652 KB |
Output is correct |
23 |
Correct |
124 ms |
28652 KB |
Output is correct |
24 |
Correct |
122 ms |
33940 KB |
Output is correct |
25 |
Correct |
127 ms |
35288 KB |
Output is correct |