# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
27084 |
2017-07-09T07:38:07 Z |
김동현(#1117) |
Swap (BOI16_swap) |
C++14 |
|
1000 ms |
217960 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n, sz, a[262144];
map<pii, int> num;
vector<int*> dp;
vector<int> s;
int mrg(int *&ret, int r, int a, int b){
ret = new int[s[a] + s[b] + 1];
ret[0] = r;
const int *av = dp[a], *bv = dp[b];
for(int i = 0, j = 1, c = 1; i < s[a]; i += j, j *= 2){
for(int k = 0; k < j; k++) ret[c++] = av[i + k];
for(int k = 0; k < j; k++) ret[c++] = bv[i + k];
}
return s[a] + s[b] + 1;
}
int f(int x, int r){
if(num.find({x, r}) != num.end()) return num[{x, r}];
if(x > sz / 2){
int *ta = new int[1];
ta[0] = r;
dp.push_back(ta);
s.push_back(1);
}
else{
int t[3] = {r, a[2 * x], a[2 * x + 1]};
sort(t, t + 3);
if(t[0] != a[2 * x + 1]){
int *ta;
s.push_back(mrg(ta, t[0], f(2 * x, r + a[2 * x] - t[0]), f(2 * x + 1, a[2 * x + 1])));
dp.push_back(ta);
}
else{
int *ta, *tb;
mrg(ta, t[0], f(2 * x, r), f(2 * x + 1, a[2 * x]));
s.push_back(mrg(tb, t[0], f(2 * x, a[2 * x]), f(2 * x + 1, r)));
for(int i = 1; ; i++){
if(ta[i] != tb[i]){
dp.push_back(ta[i] < tb[i] ? ta : tb);
if(ta[i] < tb[i]) delete[] tb;
else delete[] ta;
break;
}
}
}
}
num[{x, r}] = int(dp.size()) - 1;
return int(dp.size()) - 1;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
for(sz = 1; sz < n; sz = 2 * sz + 1);
for(int i = n + 1; i <= sz; i++) a[i] = i;
int *ans = dp[f(1, a[1])];
for(int i = 0; i < n; i++) printf("%d ", ans[i]);
puts("");
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:56:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
swap.cpp:57:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n; i++) scanf("%d", a + i);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3052 KB |
Output is correct |
2 |
Correct |
0 ms |
3052 KB |
Output is correct |
3 |
Correct |
0 ms |
3052 KB |
Output is correct |
4 |
Correct |
0 ms |
3052 KB |
Output is correct |
5 |
Correct |
0 ms |
3052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3052 KB |
Output is correct |
2 |
Correct |
0 ms |
3052 KB |
Output is correct |
3 |
Correct |
0 ms |
3052 KB |
Output is correct |
4 |
Correct |
0 ms |
3052 KB |
Output is correct |
5 |
Correct |
0 ms |
3052 KB |
Output is correct |
6 |
Correct |
0 ms |
3052 KB |
Output is correct |
7 |
Correct |
0 ms |
3052 KB |
Output is correct |
8 |
Correct |
0 ms |
3052 KB |
Output is correct |
9 |
Correct |
0 ms |
3052 KB |
Output is correct |
10 |
Correct |
0 ms |
3052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3052 KB |
Output is correct |
2 |
Correct |
0 ms |
3052 KB |
Output is correct |
3 |
Correct |
0 ms |
3052 KB |
Output is correct |
4 |
Correct |
0 ms |
3052 KB |
Output is correct |
5 |
Correct |
0 ms |
3052 KB |
Output is correct |
6 |
Correct |
0 ms |
3052 KB |
Output is correct |
7 |
Correct |
0 ms |
3052 KB |
Output is correct |
8 |
Correct |
0 ms |
3052 KB |
Output is correct |
9 |
Correct |
0 ms |
3052 KB |
Output is correct |
10 |
Correct |
0 ms |
3052 KB |
Output is correct |
11 |
Correct |
0 ms |
3316 KB |
Output is correct |
12 |
Correct |
0 ms |
3448 KB |
Output is correct |
13 |
Correct |
0 ms |
3316 KB |
Output is correct |
14 |
Correct |
3 ms |
3976 KB |
Output is correct |
15 |
Correct |
3 ms |
4108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3052 KB |
Output is correct |
2 |
Correct |
0 ms |
3052 KB |
Output is correct |
3 |
Correct |
0 ms |
3052 KB |
Output is correct |
4 |
Correct |
0 ms |
3052 KB |
Output is correct |
5 |
Correct |
0 ms |
3052 KB |
Output is correct |
6 |
Correct |
0 ms |
3052 KB |
Output is correct |
7 |
Correct |
0 ms |
3052 KB |
Output is correct |
8 |
Correct |
0 ms |
3052 KB |
Output is correct |
9 |
Correct |
0 ms |
3052 KB |
Output is correct |
10 |
Correct |
0 ms |
3052 KB |
Output is correct |
11 |
Correct |
0 ms |
3316 KB |
Output is correct |
12 |
Correct |
0 ms |
3448 KB |
Output is correct |
13 |
Correct |
0 ms |
3316 KB |
Output is correct |
14 |
Correct |
3 ms |
3976 KB |
Output is correct |
15 |
Correct |
3 ms |
4108 KB |
Output is correct |
16 |
Correct |
106 ms |
25092 KB |
Output is correct |
17 |
Correct |
119 ms |
24420 KB |
Output is correct |
18 |
Correct |
126 ms |
24984 KB |
Output is correct |
19 |
Correct |
889 ms |
108044 KB |
Output is correct |
20 |
Correct |
959 ms |
107252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3052 KB |
Output is correct |
2 |
Correct |
0 ms |
3052 KB |
Output is correct |
3 |
Correct |
0 ms |
3052 KB |
Output is correct |
4 |
Correct |
0 ms |
3052 KB |
Output is correct |
5 |
Correct |
0 ms |
3052 KB |
Output is correct |
6 |
Correct |
0 ms |
3052 KB |
Output is correct |
7 |
Correct |
0 ms |
3052 KB |
Output is correct |
8 |
Correct |
0 ms |
3052 KB |
Output is correct |
9 |
Correct |
0 ms |
3052 KB |
Output is correct |
10 |
Correct |
0 ms |
3052 KB |
Output is correct |
11 |
Correct |
0 ms |
3316 KB |
Output is correct |
12 |
Correct |
0 ms |
3448 KB |
Output is correct |
13 |
Correct |
0 ms |
3316 KB |
Output is correct |
14 |
Correct |
3 ms |
3976 KB |
Output is correct |
15 |
Correct |
3 ms |
4108 KB |
Output is correct |
16 |
Correct |
106 ms |
25092 KB |
Output is correct |
17 |
Correct |
119 ms |
24420 KB |
Output is correct |
18 |
Correct |
126 ms |
24984 KB |
Output is correct |
19 |
Correct |
889 ms |
108044 KB |
Output is correct |
20 |
Correct |
959 ms |
107252 KB |
Output is correct |
21 |
Correct |
476 ms |
97000 KB |
Output is correct |
22 |
Correct |
466 ms |
96448 KB |
Output is correct |
23 |
Correct |
493 ms |
97588 KB |
Output is correct |
24 |
Execution timed out |
1000 ms |
217960 KB |
Execution timed out |
25 |
Halted |
0 ms |
0 KB |
- |