Submission #1257051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257051		DangerNoodle7591	Xylophone (JOI18_xylophone)	C++20	100 / 100	21 ms	644 KiB

xylophone

#include <bits/stdc++.h>
using namespace std;
//#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//#define endl '\n'
//#define int long long int
#define ll long long
#define NN 5005
#define carp 10000000
#define pb push_back
#define p push
#define ins insert
#define f first
#define s second

int query(int s,int  t);
void answer(int i,int a);

int cevler[NN];
/*int query(int s,int  t){
	//cout<<s<<" "<<t<<endl;
	int mn=NN,mx=-1;
	for(int i=s;i<=t;i++){
		mn=min(mn,cevler[i]);
		mx=max(mx,cevler[i]);
	}
	//int a;cin>>a;
	return mx-mn;
}
void answer(int i,int a){
	cout<<i<<" "<<a<<endl;
	if(cevler[i]!=a)cout<<"a "<<i<<" "<<cevler[i]<<" "<<a<<endl;
	int of;
}*/

int bir_bul(int N){
	int hed=query(1,N);
	int l=2,r=N;
	int left=2;
	while(l<=r){
		int mid=(l+r)/2;
		int a=query(1,mid);
		if(a!=hed)l=mid+1;
		else{
			left=mid;
			r=mid-1;
		}
	}
	//cout<<left<<endl;
	int ans=-1;
	l=1,r=left-1;
	while(l<=r){
		int mid=(l+r)/2;
		int a=query(mid,left);
		//cout<<l<<" "<<r<<" "<<mid<<" "<<a<<endl;
		if(a!=hed)r=mid-1;
		else{
			ans=mid;
			l=mid+1;
		}
		//cout<<ans<<endl;
	}
	return ans;
}

void solve(int N){
	int mn=bir_bul(N);
	//cout<<mn<<endl;
	//return;
	set<int> st;
	st.ins(1);
	answer(mn,1);
	int a=1,b;
	if(mn!=N){
		b=1+query(mn,mn+1);
		st.ins(b);
		answer(mn+1,b);
	}
	for(int i=mn+2;i<=N;i++){
		int ok=0,x=query(i-1,i);
		int ans=0;
		if(b+x>N||st.find(b+x)!=st.end())ans=b-x;
		if(b-x<1||st.find(b-x)!=st.end())ans=b+x;
		if(ans==0){
			ok=query(i-2,i);
			if(a<b){
				if(ok==b+x-a)ans=b+x;
				else ans=b-x;
			}
			else{
				if(ok==a-b+x)ans=b-x;
				else ans=b+x;
			}
		}
		st.ins(ans);
		answer(i,ans);
		a=b;
		b=ans;
	}
	a=1;
	if(mn!=1){
		b=1+query(mn-1,mn);
		st.ins(b);
		answer(mn-1,b);
	}
	for(int i=mn-2;i>0;i--){
		int ok=0,x=query(i,i+1);
		int ans=0;
		if(b+x>N||st.find(b+x)!=st.end())ans=b-x;
		if(b-x<1||st.find(b-x)!=st.end())ans=b+x;
		if(ans==0){
			ok=query(i,i+2);
			if(a<b){
				if(ok==b+x-a)ans=b+x;
				else ans=b-x;
			}
			else{
				if(ok==a-b+x)ans=b-x;
				else ans=b+x;
			}
		}
		st.ins(ans);
		answer(i,ans);
		a=b;
		b=ans;
	}
}


/*
signed main(){
	//lalala;
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>cevler[i];
	solve(n);

}*/

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