Submission #81764

#	Time	Username	Problem	Language	Result	Execution time	Memory
81764		AngelKnows	Swap (BOI16_swap)	C++14	100 / 100	164 ms	55448 KiB

swap

#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 (stderr)

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 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32