# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
538878 |
2022-03-17T23:25:40 Z |
qwerasdfzxcl |
Swap (BOI16_swap) |
C++14 |
|
1000 ms |
194648 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> dp[200200][20][2];
int a[400400], n;
vector<int> combine(int x, int s1, int i1, int j1, int s2, int i2, int j2){
if (s1>n) return {x};
vector<int> ret = {x};
if (s2>n){
for (auto &y:dp[s1][i1][j1]) ret.push_back(y);
return ret;
}
int pt = 0;
for (int t=1;;t*=2){
for (int i=0;i<t;i++){
if (pt+i>=(int)dp[s1][i1][j1].size()) break;
ret.push_back(dp[s1][i1][j1][pt+i]);
}
for (int i=0;i<t;i++){
if (pt+i>=(int)dp[s2][i2][j2].size()) break;
ret.push_back(dp[s2][i2][j2][pt+i]);
}
pt += t;
if (pt>=(int)dp[s1][i1][j1].size() && pt>=(int)dp[s2][i2][j2].size()) break;
}
return ret;
}
void _delete(int s){
if (s>n) return;
for (int i=0;i<20;i++){
dp[s][i][0].clear();
dp[s][i][1].clear();
dp[s][i][0].shrink_to_fit();
dp[s][i][1].shrink_to_fit();
}
}
void dfs(int s, int dep, vector<pair<int, int>> C){
C.emplace_back(dep+1, 0);
if (s*2<=n){
dfs(s*2, dep+1, C);
}
if (s*2+1<=n){
C.pop_back();
C.emplace_back(dep, 1);
C.emplace_back(dep+1, 0);
dfs(s*2+1, dep+1, C);
C.pop_back();
}
C.pop_back();
reverse(C.begin(), C.end());
int cur = s, cdep = dep;
for (auto &[i, j]:C){
while(cdep>i){
cdep--; cur /= 2;
}
assert(cdep==i);
if (j==1) cur *= 2;
vector<int> v[4];
v[0] = combine(a[cur], s*2, dep+1, 0, s*2+1, dep+1, 0);
v[1] = combine(a[s*2], s*2, i, j, s*2+1, dep+1, 0);
v[2] = combine(a[s*2+1], s*2, dep+1, 0, s*2+1, i, j);
v[3] = combine(a[s*2+1], s*2, i, j, s*2+1, dep, 1);
dp[s][i][j] = *min_element(v, v+4);
if (j==1) cur /= 2;
}
_delete(s*2);
_delete(s*2+1);
}
int main(){
scanf("%d", &n);
for (int i=1;i<=n;i++) scanf("%d", a+i);
for (int i=n+1;i<=n*2+1;i++) a[i] = 1e9;
dfs(1, 1, {{1, 0}});
for (auto &x:dp[1][1][0]) printf("%d ", x);
return 0;
}
Compilation message
swap.cpp: In function 'void dfs(int, int, std::vector<std::pair<int, int> >)':
swap.cpp:60:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for (auto &[i, j]:C){
| ^
swap.cpp: In function 'int main()':
swap.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
swap.cpp:84:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | for (int i=1;i<=n;i++) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
188348 KB |
Output is correct |
2 |
Correct |
90 ms |
188348 KB |
Output is correct |
3 |
Correct |
89 ms |
188340 KB |
Output is correct |
4 |
Correct |
108 ms |
188304 KB |
Output is correct |
5 |
Correct |
93 ms |
188340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
188348 KB |
Output is correct |
2 |
Correct |
90 ms |
188348 KB |
Output is correct |
3 |
Correct |
89 ms |
188340 KB |
Output is correct |
4 |
Correct |
108 ms |
188304 KB |
Output is correct |
5 |
Correct |
93 ms |
188340 KB |
Output is correct |
6 |
Correct |
105 ms |
188308 KB |
Output is correct |
7 |
Correct |
95 ms |
188352 KB |
Output is correct |
8 |
Correct |
94 ms |
188344 KB |
Output is correct |
9 |
Correct |
96 ms |
188244 KB |
Output is correct |
10 |
Correct |
90 ms |
188348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
188348 KB |
Output is correct |
2 |
Correct |
90 ms |
188348 KB |
Output is correct |
3 |
Correct |
89 ms |
188340 KB |
Output is correct |
4 |
Correct |
108 ms |
188304 KB |
Output is correct |
5 |
Correct |
93 ms |
188340 KB |
Output is correct |
6 |
Correct |
105 ms |
188308 KB |
Output is correct |
7 |
Correct |
95 ms |
188352 KB |
Output is correct |
8 |
Correct |
94 ms |
188344 KB |
Output is correct |
9 |
Correct |
96 ms |
188244 KB |
Output is correct |
10 |
Correct |
90 ms |
188348 KB |
Output is correct |
11 |
Correct |
110 ms |
188412 KB |
Output is correct |
12 |
Correct |
122 ms |
188412 KB |
Output is correct |
13 |
Correct |
117 ms |
188324 KB |
Output is correct |
14 |
Correct |
99 ms |
188420 KB |
Output is correct |
15 |
Correct |
98 ms |
188388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
188348 KB |
Output is correct |
2 |
Correct |
90 ms |
188348 KB |
Output is correct |
3 |
Correct |
89 ms |
188340 KB |
Output is correct |
4 |
Correct |
108 ms |
188304 KB |
Output is correct |
5 |
Correct |
93 ms |
188340 KB |
Output is correct |
6 |
Correct |
105 ms |
188308 KB |
Output is correct |
7 |
Correct |
95 ms |
188352 KB |
Output is correct |
8 |
Correct |
94 ms |
188344 KB |
Output is correct |
9 |
Correct |
96 ms |
188244 KB |
Output is correct |
10 |
Correct |
90 ms |
188348 KB |
Output is correct |
11 |
Correct |
110 ms |
188412 KB |
Output is correct |
12 |
Correct |
122 ms |
188412 KB |
Output is correct |
13 |
Correct |
117 ms |
188324 KB |
Output is correct |
14 |
Correct |
99 ms |
188420 KB |
Output is correct |
15 |
Correct |
98 ms |
188388 KB |
Output is correct |
16 |
Correct |
554 ms |
190640 KB |
Output is correct |
17 |
Correct |
524 ms |
190748 KB |
Output is correct |
18 |
Correct |
545 ms |
190612 KB |
Output is correct |
19 |
Correct |
521 ms |
190520 KB |
Output is correct |
20 |
Correct |
520 ms |
190536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
188348 KB |
Output is correct |
2 |
Correct |
90 ms |
188348 KB |
Output is correct |
3 |
Correct |
89 ms |
188340 KB |
Output is correct |
4 |
Correct |
108 ms |
188304 KB |
Output is correct |
5 |
Correct |
93 ms |
188340 KB |
Output is correct |
6 |
Correct |
105 ms |
188308 KB |
Output is correct |
7 |
Correct |
95 ms |
188352 KB |
Output is correct |
8 |
Correct |
94 ms |
188344 KB |
Output is correct |
9 |
Correct |
96 ms |
188244 KB |
Output is correct |
10 |
Correct |
90 ms |
188348 KB |
Output is correct |
11 |
Correct |
110 ms |
188412 KB |
Output is correct |
12 |
Correct |
122 ms |
188412 KB |
Output is correct |
13 |
Correct |
117 ms |
188324 KB |
Output is correct |
14 |
Correct |
99 ms |
188420 KB |
Output is correct |
15 |
Correct |
98 ms |
188388 KB |
Output is correct |
16 |
Correct |
554 ms |
190640 KB |
Output is correct |
17 |
Correct |
524 ms |
190748 KB |
Output is correct |
18 |
Correct |
545 ms |
190612 KB |
Output is correct |
19 |
Correct |
521 ms |
190520 KB |
Output is correct |
20 |
Correct |
520 ms |
190536 KB |
Output is correct |
21 |
Execution timed out |
1091 ms |
194648 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |