Submission #764640

#	Time	Username	Problem	Language	Result	Execution time	Memory
764640		vjudge1	Xylophone (JOI18_xylophone)	C++17	100 / 100	61 ms	328 KiB

xylophone

#include "xylophone.h"
//#include<bits/stdc++.h>
using namespace std;
/*
#define taskname "template"
#define ll long long
#define ld double
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int> 
#define vii vector<pii>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll rd(ll min1,ll max1){
	assert(min1<=max1);
	ll res=rng()*1LL*rng()%(max1-min1+1);
	if(res<0) res=-res;
	return min1+res;
}
*/
const int MN=5e3+5;

int arr[MN],ans[MN];
bool check[MN];
bool check2[MN];
int limit;
/*
void stress(int n){
	for(int i=1;i<=n;++i){
		ans[i]=0;
		check[i]=false;
	}
	if(n<=2){
		ans[1]=1;
		ans[2]=2;
		return;
	}
	int idx=rd(2,n);
	ans[idx]=n; //cout<<idx<<'\n';
//	cout<<idx<<endl;
//	if(1>idx-1) cout<<"!!!!!!!!!!!!!!!!! "<<idx<<endl;
	int idx1=rd(1,idx-1);
	ans[idx1]=1;
	check[1]=check[n]=true;
	
	for(int i=1;i<=n;++i){
		if(ans[i]) continue;
		if(2>n-1) cout<<"Case "<<i<<": "<<endl;
		ll res=rd(2,n-1);
		if(check[res]){
			--i; continue;
		}
		check[res]=true; ans[i]=res;
	}
//	ans[1]=2; ans[2]=1; ans[3]=3;
//	ans[1]=3; ans[2]=1; ans[3]=2; ans[4]=5; ans[5]=4; 
//	ans[6]=10; ans[7]=2; ans[8]=8; ans[9]=5; ans[10]=9;
}

int query(int tl,int tr){
	return *max_element(ans+tl, ans+tr+1) - *min_element(ans+tl, ans+tr+1);
}

void answer(int p,int value){
	arr[p]=value;
}
*/
void solve(int n){
	if(n==1){
		answer(1,1); return;
	}
	for(int i=1;i<=n;++i){
		check2[i]=false;
	}
	limit=10000;
	int l=1,r=n;
	/*
	int idx=n-1;
	for(int i=2;i<idx;++i){
		int res=query(i,n);
		if(res!=n-1){
			idx=i-1; break;
		}
	}
	*/
	while(l<r){
		int mid=l+r>>1;
		int res=query(mid,n); --limit;
//		cout<<"Case "<<mid<<' '<<n<<": "<<res<<'\n';
		
		if(res==n-1) l=mid+1;
		else r=mid;
	}
	int idx=l-1;
	
//	cout<<idx<<'\n';
	arr[idx]=1;
	check2[1]=true;
	l=idx-2,r=idx+2;
	
	if(idx>1){
		int res=query(idx-1,idx); --limit;
		arr[idx-1]=res+1;
		check2[res+1]=true;
	}
	int res=query(idx,idx+1); --limit;
	arr[idx+1]=res+1;
	check2[res+1]=true;
	
	for(int i=l;i>=1;--i){
		int res=query(i,i+1); --limit;
		if(arr[i+1]+res>=n||arr[i+1]+res<=1||check2[arr[i+1]+res]){
			arr[i]=arr[i+1]-res;
			check2[arr[i+1]-res]=true; continue;
		}
		if(arr[i+1]-res>=n||arr[i+1]-res<=1||check2[arr[i+1]-res]){
			arr[i]=arr[i+1]+res;
			check2[arr[i+1]+res]=true; continue;
		}
		if(limit==i-1+(n-r+1)){
			if(!check2[arr[i+1]+res]&&arr[i+1]+res<n){
				arr[i]=arr[i+1]+res;
				check2[arr[i+1]+res]=true;
			}
			else{
				arr[i]=arr[i+1]-res;
				check2[arr[i+1]-res]=true;
			}
		}
		else{
			int res2=query(i,i+2); --limit;
//			cout<<"Case "<<i<<": "<<res<<' '<<res2<<endl;
			if(res==res2){
				if(arr[i+2]<arr[i+1]) arr[i]=arr[i+1]-res;
				else arr[i]=arr[i+1]+res;
			}
			else{
				if(arr[i+1]>arr[i+2]){
					if(res2==arr[i+1]-arr[i+2]) arr[i]=arr[i+1]-res;
					else arr[i]=arr[i+1]+res;
				}
				else{
					if(res2==arr[i+2]-arr[i+1]) arr[i]=arr[i+1]+res;
					else arr[i]=arr[i+1]-res;
				}
			}
			check2[arr[i]]=true;
		}
	}
	for(int i=r;i<=n;++i){
		int res=query(i-1,i); --limit;
		if(arr[i-1]+res>n||arr[i-1]+res<=1||check2[arr[i-1]+res]){
//			cout<<"mmb"<<'\n';
			arr[i]=arr[i-1]-res;
			check2[arr[i-1]-res]=true; continue;
		}
		if(arr[i-1]-res>n||arr[i-1]-res<=1||check2[arr[i-1]-res]){
//			cout<<"mmg"<<'\n';
			arr[i]=arr[i-1]+res;
			check2[arr[i-1]+res]=true; continue;
		}
		if(limit==n-i){
			if(!check2[arr[i-1]+res]&&arr[i-1]+res<=n){
				arr[i]=arr[i-1]+res;
				check2[arr[i-1]+res]=true;
			}
			else{
				arr[i]=arr[i-1]+res;
				check2[arr[i-1]-res]=true;
			}
		}
		else{
			int res2=query(i-2,i); --limit;
//			cout<<"Case "<<i<<": "<<res<<' '<<res2<<'\n';
			if(res==res2){
				if(arr[i-2]<arr[i-1]) arr[i]=arr[i-1]-res;
				else arr[i]=arr[i-1]+res;
			}
			else{
				if(arr[i-2]<arr[i-1]){
					if(res2==arr[i-1]-arr[i-2]) arr[i]=arr[i-1]-res;
					else arr[i]=arr[i-1]+res;
				}
				else{
					if(res2==arr[i-2]-arr[i-1]) arr[i]=arr[i-1]+res;
					else arr[i]=arr[i-1]-res;
				}
			}
			check2[arr[i]]=true;
		}
	}
	for(int i=1;i<=n;++i){
		answer(i,arr[i]);
	}
}
/*
int test(int n){
	for(int i=1;i<=n;++i){
		if(arr[i]!=ans[i]){
			return 0;
		}
	}
	return 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("output.txt","w",stdout);
    /*
    freopen(taskname".inp","r",stdin);
    freopen(taskname".out","w",stdout);
    
    int last=1;
    for(int numtest=1;numtest<=(int)100;++numtest){
    	cout<<"Running on test "<<numtest<<": ";
    	int n; n=rd(1,10);
    	stress(n);
    	for(int i=1;i<=n;++i){
    		cout<<ans[i]<<' ';
		} cout<<endl;
    	solve(n);
    	last&=test(n);
    	cout<<"Question left: "<<limit<<endl<<endl;
    	if(!last){
    		cout<<"Wrong answer on test "<<numtest<<endl; 
    		cout<<"Your array:   ";
    		for(int i=1;i<=n;++i){
    			cout<<arr[i]<<' ';
			}cout<<endl;
			cout<<"Answer array: ";
			for(int i=1;i<=n;++i){
    			cout<<ans[i]<<' ';
			}cout<<endl;
			return 0;
		}
	}
	cout<<"Accepted!";
}
*/

Compilation message (stderr)

xylophone.cpp:214:5: warning: "/*" within comment [-Wcomment]
  214 |     /*
      |      
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |   int mid=l+r>>1;
      |           ~^~

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53