Submission #199037

#	Time	Username	Problem	Language	Result	Execution time	Memory
199037		TadijaSebez	Swap (BOI16_swap)	C++11	100 / 100	76 ms	6904 KiB

swap

#include <bits/stdc++.h>
using namespace std;
void ckmn(int &a,int b){a=min(a,b);}
const int N=400050;
int a[N],t[N],ans[N];
int Get(int i){
	int ans=1e9;
	for(;i;i>>=1){
		if(t[i]!=1)ckmn(ans,a[i]);
		if(t[i]==0)break;
		if((i&1) && t[i^1]!=0){
			ckmn(ans,a[i^1]);
			if(t[i^1]==1)break;
		}
	}
	return ans;
}
void Set(int i,int f){
	for(;i;i>>=1){
		if(a[i]==f){
			t[i]=0;
			break;
		}
		if(i&1){
			if(a[i^1]==f){
				t[i]=t[i^1]=1;
				break;
			}else t[i^1]=0;
		}
		t[i]=1;
	}
}
int main(){
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),t[i]=2;
	t[1]=0;
	for(int i=n+1;i<=n*2+1;i++)a[i]=1e9;
	for(int i=1;i<=n;i++){
		int gt=Get(i);
		ans[i]=min({a[i<<1],a[i<<1|1],gt});
		if(ans[i]==gt)
			t[i<<1]=0,
			t[i<<1|1]=0,
			Set(i,gt);
		if(ans[i]==a[i<<1])
			t[i<<1]=1,
			t[i<<1|1]=0;
		if(ans[i]==a[i<<1|1])
			t[i<<1|1]=1;
	}
	for(int i=1;i<=n;i++)printf("%i%c",ans[i],i==n?'\n':' ');
	return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
swap.cpp:36:40: 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("%i",&a[i]),t[i]=2;
                       ~~~~~~~~~~~~~~~~~^~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32