# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
27105 |
2017-07-09T09:18:04 Z |
gs14004 |
Swap (BOI16_swap) |
C++14 |
|
783 ms |
168568 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
int n, a[530000];
map<int, int> sol[200005];
int solve(int x, int r){
if(x > n) return -1;
if(sol[x].find(r) != sol[x].end()) return sol[x][r];
int minval = min({r, a[2*x], a[2*x+1]});
if(minval == r){
solve(2*x, a[2*x]);
solve(2*x+1, a[2*x+1]);
return sol[x][r] = x;
}
else if(minval == a[2*x]){
int ret = solve(2*x, r);
solve(2*x+1, a[2*x+1]);
return sol[x][r] = ret;
}
else{
int k1 = solve(2*x, r);
int k2 = solve(2*x+1, a[2*x]);
int k3 = solve(2*x, a[2*x]);
int k4 = solve(2*x+1, r);
if(min(k1, k2) < min(k3, k4)){
return sol[x][r] = k1;
}
if(min(k1, k2) > min(k3, k4)){
return sol[x][r] = k4;
}
if(r < a[2*x]){
if(k1 < k4){
return sol[x][r] = k1;
}
else{
return sol[x][r] = k4;
}
}
else{
if(k2 < k3){
return sol[x][r] = k1;
}
else{
return sol[x][r] = k4;
}
}
}
}
void fmerge(vector<int> &ret, vector<int> &v1, vector<int> &v2){
int pnt = 0;
for(int i=1; pnt < max(v1.size(), v2.size()); i<<=1){
for(int j=pnt; j<pnt + i && j < v1.size(); j++){
ret.push_back(v1[j]);
}
for(int j=pnt; j<pnt + i && j < v2.size(); j++){
ret.push_back(v2[j]);
}
pnt+=i;
}
}
vector<int> track(int x, int r){
if(x > n) return vector<int>();
int minval = min({r, a[2*x], a[2*x+1]});
if(minval == r){
auto a1 = vector<int>{r};
auto a2 = track(2*x, a[2*x]);
auto a3 = track(2*x+1, a[2*x+1]);
fmerge(a1, a2, a3);
return a1;
}
else if(minval == a[2*x]){
auto a1 = vector<int>{a[2*x]};
auto a2 = track(2*x, r);
auto a3 = track(2*x+1, a[2*x+1]);
fmerge(a1, a2, a3);
return a1;
}
else{
int k1 = solve(2*x, r);
int k4 = solve(2*x+1, r);
if(sol[x][r] == k1){
auto a1 = vector<int>{a[2*x+1]};
auto a2 = track(2*x, r);
auto a3 = track(2*x+1, a[2*x]);
fmerge(a1, a2, a3);
return a1;
}
else{
auto a1 = vector<int>{a[2*x+1]};
auto a2 = track(2*x, a[2*x]);
auto a3 = track(2*x+1, r);
fmerge(a1, a2, a3);
return a1;
}
}
}
int main(){
memset(a, 0x3f, sizeof(a));
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
solve(1, a[1]);
auto w = track(1, a[1]);
for(auto &i : w){
printf("%d ",i);
}
}
Compilation message
swap.cpp: In function 'void fmerge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; pnt < max(v1.size(), v2.size()); i<<=1){
^
swap.cpp:57:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=pnt; j<pnt + i && j < v1.size(); j++){
^
swap.cpp:60:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=pnt; j<pnt + i && j < v2.size(); j++){
^
swap.cpp: In function 'std::vector<int> track(int, int)':
swap.cpp:86:7: warning: unused variable 'k4' [-Wunused-variable]
int k4 = solve(2*x+1, r);
^
swap.cpp: In function 'int main()':
swap.cpp:107:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
swap.cpp:109:20: 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 |
3 ms |
13472 KB |
Output is correct |
2 |
Correct |
0 ms |
13472 KB |
Output is correct |
3 |
Correct |
0 ms |
13472 KB |
Output is correct |
4 |
Correct |
3 ms |
13472 KB |
Output is correct |
5 |
Correct |
3 ms |
13472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13472 KB |
Output is correct |
2 |
Correct |
0 ms |
13472 KB |
Output is correct |
3 |
Correct |
0 ms |
13472 KB |
Output is correct |
4 |
Correct |
3 ms |
13472 KB |
Output is correct |
5 |
Correct |
3 ms |
13472 KB |
Output is correct |
6 |
Correct |
6 ms |
13472 KB |
Output is correct |
7 |
Correct |
3 ms |
13472 KB |
Output is correct |
8 |
Correct |
0 ms |
13472 KB |
Output is correct |
9 |
Correct |
0 ms |
13472 KB |
Output is correct |
10 |
Correct |
3 ms |
13472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13472 KB |
Output is correct |
2 |
Correct |
0 ms |
13472 KB |
Output is correct |
3 |
Correct |
0 ms |
13472 KB |
Output is correct |
4 |
Correct |
3 ms |
13472 KB |
Output is correct |
5 |
Correct |
3 ms |
13472 KB |
Output is correct |
6 |
Correct |
6 ms |
13472 KB |
Output is correct |
7 |
Correct |
3 ms |
13472 KB |
Output is correct |
8 |
Correct |
0 ms |
13472 KB |
Output is correct |
9 |
Correct |
0 ms |
13472 KB |
Output is correct |
10 |
Correct |
3 ms |
13472 KB |
Output is correct |
11 |
Correct |
6 ms |
13604 KB |
Output is correct |
12 |
Correct |
6 ms |
13604 KB |
Output is correct |
13 |
Correct |
6 ms |
13604 KB |
Output is correct |
14 |
Correct |
6 ms |
13868 KB |
Output is correct |
15 |
Correct |
3 ms |
13868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13472 KB |
Output is correct |
2 |
Correct |
0 ms |
13472 KB |
Output is correct |
3 |
Correct |
0 ms |
13472 KB |
Output is correct |
4 |
Correct |
3 ms |
13472 KB |
Output is correct |
5 |
Correct |
3 ms |
13472 KB |
Output is correct |
6 |
Correct |
6 ms |
13472 KB |
Output is correct |
7 |
Correct |
3 ms |
13472 KB |
Output is correct |
8 |
Correct |
0 ms |
13472 KB |
Output is correct |
9 |
Correct |
0 ms |
13472 KB |
Output is correct |
10 |
Correct |
3 ms |
13472 KB |
Output is correct |
11 |
Correct |
6 ms |
13604 KB |
Output is correct |
12 |
Correct |
6 ms |
13604 KB |
Output is correct |
13 |
Correct |
6 ms |
13604 KB |
Output is correct |
14 |
Correct |
6 ms |
13868 KB |
Output is correct |
15 |
Correct |
3 ms |
13868 KB |
Output is correct |
16 |
Correct |
36 ms |
19736 KB |
Output is correct |
17 |
Correct |
33 ms |
19812 KB |
Output is correct |
18 |
Correct |
39 ms |
19840 KB |
Output is correct |
19 |
Correct |
136 ms |
47620 KB |
Output is correct |
20 |
Correct |
146 ms |
47356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
13472 KB |
Output is correct |
2 |
Correct |
0 ms |
13472 KB |
Output is correct |
3 |
Correct |
0 ms |
13472 KB |
Output is correct |
4 |
Correct |
3 ms |
13472 KB |
Output is correct |
5 |
Correct |
3 ms |
13472 KB |
Output is correct |
6 |
Correct |
6 ms |
13472 KB |
Output is correct |
7 |
Correct |
3 ms |
13472 KB |
Output is correct |
8 |
Correct |
0 ms |
13472 KB |
Output is correct |
9 |
Correct |
0 ms |
13472 KB |
Output is correct |
10 |
Correct |
3 ms |
13472 KB |
Output is correct |
11 |
Correct |
6 ms |
13604 KB |
Output is correct |
12 |
Correct |
6 ms |
13604 KB |
Output is correct |
13 |
Correct |
6 ms |
13604 KB |
Output is correct |
14 |
Correct |
6 ms |
13868 KB |
Output is correct |
15 |
Correct |
3 ms |
13868 KB |
Output is correct |
16 |
Correct |
36 ms |
19736 KB |
Output is correct |
17 |
Correct |
33 ms |
19812 KB |
Output is correct |
18 |
Correct |
39 ms |
19840 KB |
Output is correct |
19 |
Correct |
136 ms |
47620 KB |
Output is correct |
20 |
Correct |
146 ms |
47356 KB |
Output is correct |
21 |
Correct |
216 ms |
38828 KB |
Output is correct |
22 |
Correct |
183 ms |
38860 KB |
Output is correct |
23 |
Correct |
176 ms |
38872 KB |
Output is correct |
24 |
Correct |
783 ms |
168436 KB |
Output is correct |
25 |
Correct |
679 ms |
168568 KB |
Output is correct |