| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 260284 |
2020-08-10T02:58:06 Z |
arnold518 |
Swap (BOI16_swap) |
C++14 |
|
8 ms |
9728 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
int N, A[MAXN+10];
vector<int> V[MAXN+10], C[MAXN+10];
int dep[MAXN+10];
bool vis[MAXN+10][36];
int dp[MAXN+10][36], memo[MAXN+10][36], ans[MAXN+10];
int solve(int now, int pp)
{
int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
if(vis[now][qq]) return dp[now][qq];
vis[now][qq]=1;
int &ret=dp[now][qq];
int &mem=memo[now][qq];
if(now*2>N)
{
ret=now;
return ret;
}
if(now*2+1>N)
{
if(A[pp]>A[now*2]) ret=now*2;
else ret=now;
return ret;
}
if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
{
ret=now;
return ret;
}
if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
{
ret=solve(now*2, pp);
return ret;
}
if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
{
int p1=solve(now*2, pp), q1=solve(now*2+1, now*2);
int p2=solve(now*2, now*2), q2=solve(now*2+1, pp);
if(A[pp]<A[now*2]) assert(p1<=p2);
if(A[pp]>A[now*2]) assert(p1>=p2);
if(A[now*2]<A[pp]) assert(q1<=q2);
if(A[now*2]>A[pp]) assert(q1>=q2);
int flag;
if(min(dep[p1], dep[p2])<=min(dep[q1], dep[q2]))
{
if(p1==p2)
{
if(A[pp]<A[now*2]) flag=1;
else flag=2;
}
if(p1<p2) flag=1;
if(p1>p2) flag=2;
}
else
{
if(q1==q2)
{
if(A[now*2]<A[pp]) flag=1;
else flag=2;
}
if(q1<q2) flag=1;
else flag=2;
}
mem=flag;
if(flag==1) ret=p1;
else ret=q2;
return ret;
}
}
void restore(int now, int pp)
{
int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
solve(now, pp);
int mem=memo[now][qq];
if(now*2>N)
{
ans[now]=A[pp];
return;
}
if(now*2+1>N)
{
if(A[pp]<A[now*2]) ans[now]=A[pp], ans[now*2]=A[now*2];
else ans[now]=A[now*2], ans[now*2]=A[pp];
return;
}
if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
{
ans[now]=A[pp];
restore(now*2, now*2);
restore(now*2+1, now*2+1);
return;
}
if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
{
ans[now]=A[now*2];
restore(now*2, pp);
restore(now*2+1, now*2+1);
return;
}
if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
{
assert(mem==1 || mem==2);
ans[now]=A[now*2+1];
if(mem==1) { restore(now*2, pp); restore(now*2+1, now*2); }
else { restore(now*2, now*2); restore(now*2+1, pp); }
}
}
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
for(int i=1; i<=N; i++)
{
int now=i; dep[i]=1;
while(now!=1)
{
dep[i]++;
V[i].push_back(now);
C[now].push_back(i);
if(now%2) V[i].push_back(now-1);
now/=2;
}
C[1].push_back(i);
V[i].push_back(1);
reverse(V[i].begin(), V[i].end());
}
restore(1, 1);
for(int i=1; i<=N; i++) printf("%d ", ans[i]);
}
Compilation message
swap.cpp: In function 'int solve(int, int)':
swap.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
swap.cpp: In function 'int main()':
swap.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
swap.cpp:127:31: 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]);
~~~~~^~~~~~~~~~~~~
swap.cpp: In function 'int solve(int, int)':
swap.cpp:77:6: warning: 'flag' may be used uninitialized in this function [-Wmaybe-uninitialized]
mem=flag;
~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
