| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 35295 |
2017-11-19T19:20:07 Z |
imaxblue |
Swap (BOI16_swap) |
C++14 |
|
0 ms |
5920 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()
int n, t,
type[200005], best[200005], par[200005], p[200005], a[200005];
int swp(int X, int Y){
t=p[X]; p[X]=p[Y]; p[Y]=t;
a[p[X]]=X; a[p[Y]]=Y;
}
int get(int N){
int P=par[N];
N=p[N];
//cout << best[0] << ' ' << N << ' ' << P << endl;
int hi=N;
while(N!=P){
N=N/2;
hi=min(hi, best[N]);
};
return hi;
}
int del(int N, int P){
best[N]=(1 << 30);
N*=2;
while(N!=P){
N=N/2;
if (type[N]==2){
best[N]=best[N*2];
}
if (type[N]==3){
best[N]=min(best[N*2], best[N*2+1]);
}
}
}
int main(){
cin >> n;
type[0]=1; best[0]=(1<<30);
fox1(l, n){
best[l]=l;
cin >> a[l];
p[a[l]]=l;
par[a[l]]=l/2;
}
//fox1(l, n) cout << par[l] << ' ' ;cout << endl;
fox1(l, n){
t=get(l);
//cout << l << ' ' << t << endl;
swp(a[t], l);
if (t==par[l]){
type[t]=2+(p[l]%2);
del(t, par[l]);
//fox1(l, n) cout << a[l] << ' '; cout << endl;
continue;
}
type[t]=1;
del(t, par[l]);
//fox1(l, n) cout << a[l] << ' '; cout << endl;
}
fox1(l, n) cout << a[l] << ' ';
return 0;
}
Compilation message
swap.cpp: In function 'int swp(int, int)':
swap.cpp:32:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
swap.cpp: In function 'int del(int, int)':
swap.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
