oj.uz

Submission #81764

# Submission time Handle Problem Language Result Execution time Memory
81764 2018-10-26T13:18:54 Z AngelKnows Swap (BOI16_swap) C++14
100 / 100
 164 ms 55448 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define sz(x) ((int)(x).size())
 
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=200000+10;
const double eps=1e-5;
const int mo=1e9+7;

int n;
int a[N],b[N];
int p=1;
int q[N][46],len[N];
// q[i]存放在i处的预约元素的原来位置 
int mn,pos;
bool used[N],vis[N];

struct edge {
	int to,nxt;
} e[2*N];
int tot;
int head[N];

int cnt;
int dn[N];
int last[N];
int fa[N];


int o[N];
// o[i]=1表示第i点取了，o[i]=2表示第i点确定不取，o[i]=0表示不确定 

int dir(int x,int y) {
	// 判断y是x的左后代还是右后代
	// 要先保证y是x的后代 
	if (last[2*x]<dn[y]) {
		return 1;
		// 右后代 
	} else return 0; // 左后代 
}
void insert(int x,int y) {
	e[++tot].to=y,e[tot].nxt=head[x],head[x]=tot;
	e[++tot].to=x,e[tot].nxt=head[y],head[y]=tot;
}
void dfs(int x) {
	dn[x]=++cnt;
	int y;
	for (int i=head[x];i;i=e[i].nxt) {
		y=e[i].to;
		if (y!=fa[x]) {
			fa[y]=x;
			dfs(y);
		}
	}
	last[x]=cnt;
}
bool ok(int s,int t) {
	if (s==t) {
		if (o[s]!=1&&(2*s>n||o[2*s]!=1)&&(2*s+1>n||o[2*s+1]!=1)) {
			return 1;
		} else return 0;
	}
	if (s>t) {
		if (s%2==0) {
			if (o[s]!=2&&(s+1>n||o[s+1]!=1)) return 1;
			else return 0;
		} else {
			if (o[s]!=2) return 1;
			else return 0;
		}
	}
	bool f=0;
 	if (last[s]<dn[t]) {
		if (o[s]==2) return 0;	
		s++;
		if (s==t) {
			if (o[t]!=2&&(2*t>n||o[2*t]!=1)&&(2*t+1>n||o[2*t+1]!=1)) return 1;
			else return 0;
		} else {
			if (o[s]==2) return 0;
			if (!dir(s,t)) s*=2;
			else s=2*s+1;
		}
	} else {
		if (o[s]==1) return 0;
		if (!dir(s,t)) s*=2;
		else s=2*s+1;
	}
	for (;;) {
		if (o[s]==2) return 0;
		if (s%2) if (o[s-1]==1) return 0;
		if (s==t) break;
		if (!dir(s,t)) s*=2;
		else s=2*s+1; 
	}
	if ((2*t<=n&&o[2*t]==1)||(2*t+1<=n&&o[2*t+1]==1)) return 0;
	return 1;
}
void walk(int s,int t) {
	if (s==t) {
		o[s]=2;
		if (2*s<=n) o[2*s]=2;
		if (2*s+1<=n) o[2*s+1]=2;
		return;
	}
	if (s>t) {
		if (s%2==0) {
			o[s]=1;
			if (s+1<=n) o[s+1]=2;
		} else {
			o[s]=1;
		}
		return;
	}
	if (last[s]<dn[t]) {
		o[s]=1;
		s++;
		if (s==t) {
			o[t]=1;
			if (2*t<=n) o[2*t]=2;
			if (2*t+1<=n) o[2*t+1]=2;
			return;
		} else {
			o[s]=1;
			if (!dir(s,t)) s*=2;
			else s=2*s+1;
		}
	} else {
		o[s]=2;
		if (!dir(s,t)) s*=2;
		else s=2*s+1;
	}
	for (;;) {
		o[s]=1;
		if (s%2) o[s-1]=2;
		if (s==t) break;
		if (!dir(s,t)) s*=2;
		else s=2*s+1; 
	}
	if (2*t<=n) o[2*t]=2;
	if (2*t+1<=n) o[2*t+1]=2;
}
int main() {
 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    FOR(i,n) scanf("%d",&a[i]);
    FOR(i,n) {
    	if (2*i+1<=n) insert(i,2*i+1);
    	if (2*i<=n) insert(i,2*i);
	}
	dfs(1);
    q[1][++len[1]]=1;
    REP(i,2,n) {
    	//cout<<i<<endl;
    	q[i][++len[i]]=i;
    	q[i/2][++len[i/2]]=i;
		
    	if (i==2*p+1) {
    		mn=inf,pos=0; 
    		FOR(j,len[p]) if (!used[a[q[p][j]]]&&a[q[p][j]]<mn) {
    			//cout<<q[p][j]<<" "<<p<<endl;
    			if (ok(q[p][j],p)) {
    				mn=a[q[p][j]];
    				pos=q[p][j];
				}
			}
			walk(pos,p);
			b[p]=a[pos];
			used[b[p]]=1;
			int pp;
			FOR(j,len[p]) {
				pp=q[p][j];
				if (pos!=pp&&!used[a[pp]]&&!vis[a[pp]]) {
					vis[a[pp]]=1;
					if (pp!=2*p+1) q[i-1][++len[i-1]]=pp;
					q[i][++len[i]]=pp;
				}
			}
			FOR(j,len[p]) vis[a[q[p][j]]]=0;
			++p;
		}
	}
	while (p<=n) {
		
		mn=inf,pos=0; 
		FOR(j,len[p]) if (!used[a[q[p][j]]]&&a[q[p][j]]<mn) {
			//cout<<q[p][j]<<" "<<p<<endl;
			if (ok(q[p][j],p)) {
				mn=a[q[p][j]];
				pos=q[p][j];
			}
		}
		//FOR(i,n) cout<<o[i]<<" ";
		walk(pos,p);
		b[p]=a[pos];
		used[b[p]]=1;
		int pp;
		FOR(j,len[p]) {
			pp=q[p][j];
			if (pos!=pp&&!used[a[pp]]&&!vis[a[pp]]) {
				vis[a[pp]]=1;
				if (pp!=2*p+1) if (2*p<=n) q[2*p][++len[2*p]]=pp;
			}
		}
		FOR(j,len[p]) vis[a[q[p][j]]]=0;
		++p;
	}
	//FOR(i,n) cout<<o[i]<<endl;
	FOR(i,n) printf("%d ",b[i]);
	printf("\n");
	return 0;
}

Compilation message

swap.cpp: In function 'bool ok(int, int)':
swap.cpp:83:7: warning: unused variable 'f' [-Wunused-variable]
  bool f=0;
       ^
swap.cpp: In function 'int main()':
swap.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
swap.cpp:163:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i,n) scanf("%d",&a[i]);
              ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 2 ms 624 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 2 ms 624 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 904 KB Output is correct
12 Correct 3 ms 908 KB Output is correct
13 Correct 3 ms 912 KB Output is correct
14 Correct 3 ms 916 KB Output is correct
15 Correct 3 ms 920 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 2 ms 624 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 904 KB Output is correct
12 Correct 3 ms 908 KB Output is correct
13 Correct 3 ms 912 KB Output is correct
14 Correct 3 ms 916 KB Output is correct
15 Correct 3 ms 920 KB Output is correct
16 Correct 47 ms 12700 KB Output is correct
17 Correct 35 ms 13000 KB Output is correct
18 Correct 42 ms 13276 KB Output is correct
19 Correct 32 ms 13616 KB Output is correct
20 Correct 31 ms 13900 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 2 ms 624 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 904 KB Output is correct
12 Correct 3 ms 908 KB Output is correct
13 Correct 3 ms 912 KB Output is correct
14 Correct 3 ms 916 KB Output is correct
15 Correct 3 ms 920 KB Output is correct
16 Correct 47 ms 12700 KB Output is correct
17 Correct 35 ms 13000 KB Output is correct
18 Correct 42 ms 13276 KB Output is correct
19 Correct 32 ms 13616 KB Output is correct
20 Correct 31 ms 13900 KB Output is correct
21 Correct 164 ms 50376 KB Output is correct
22 Correct 139 ms 51668 KB Output is correct
23 Correct 139 ms 53056 KB Output is correct
24 Correct 132 ms 54132 KB Output is correct
25 Correct 130 ms 55448 KB Output is correct