Submission #1256471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256471		DangerNoodle7591	Xylophone (JOI18_xylophone)	C++20	0 / 100	2 ms	2752 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 10000
#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 query(int s,int  t){
	cout<<s<<" "<<t<<endl;
	int a;cin>>a;
	return a;
}
void answer(int i,int a){
	cout<<i<<" "<<a<<endl;
}*/

pair<vector<int>,vector<int>> arr[NN],seg[NN*4];
int deg[NN*4];
int val[NN];

void yap(int x,int b,int fark,int kim){
	int okey_sol=0,okey_sag=0;
	if(seg[x].f.size()==0)okey_sol=1;
	if(seg[x].s.size()==0)okey_sag=1;

	if(seg[x].f.size()){
		for(auto u:seg[x].f){
			if(u<0||u>fark){okey_sol=1;break;}
		}
	}	
	if(seg[x].s.size()){
		for(auto u:seg[x].s){
			if(u<0||u>fark){okey_sag=1;break;}
		}
	}
	if(kim==1){
		if(okey_sol)seg[x].f=seg[x*2].f;
		if(okey_sag)seg[x].s=seg[x*2].s;
	}
	else{
		if(okey_sol)seg[x].f=seg[x*2+1].f;
		if(okey_sag)seg[x].s=seg[x*2+1].s;
		if(okey_sol)reverse(seg[x].f.begin(),seg[x].f.end());
		if(okey_sag)reverse(seg[x].s.begin(),seg[x].s.end());
		reverse(seg[b].f.begin(),seg[b].f.end());
		reverse(seg[b].s.begin(),seg[b].s.end());
	}
	if(okey_sol){
		set<int> st;
		int sonn=0;
		for(auto u:seg[x].f){
			sonn=u;
			st.ins(u);
		}
		int ok=1,geld=1;
		int son=sonn;
		for(auto u:seg[b].f){
			if(geld){
				son-=u;
				geld=0;continue;
			}
			int yeni=u+son;
			if(st.find(yeni)!=st.end()||yeni<0||yeni>fark){
				ok=0;break;
			}
		}
		if(ok){
			geld=1;
			for(auto u:seg[b].f){
				if(geld){geld=0;continue;}
				seg[x].f.pb(u+son);
			}
		}
		else{
			geld=1;
			for(auto u:seg[b].s){
				if(geld){
					sonn-=u;
					geld=0;continue;
				}
				seg[x].f.pb(u+sonn);
			}
		}
	}
	if(okey_sag){
		set<int> st;
		int sonn=0;
		for(auto u:seg[x].s){
			sonn=u;
			st.ins(u);
		}
		int ok=1,geld=1;
		int son=sonn;
		for(auto u:seg[b].f){
			if(geld){
				son-=u;
				geld=0;continue;
			}
			int yeni=u+son;
			if(st.find(yeni)!=st.end()||yeni<0||yeni>fark){
				ok=0;break;
			}
		}
		if(ok){
			geld=1;
			for(auto u:seg[b].f){
				if(geld){geld=0;continue;}
				seg[x].s.pb(u+son);
			}
		}
		else{
			geld=1;
			for(auto u:seg[b].s){
				if(geld){
					sonn-=u;
					geld=0;continue;
				}
				seg[x].s.pb(u+sonn);
			}
		}
	}
	if(kim!=1){
		if(okey_sol)reverse(seg[x].f.begin(),seg[x].f.end());
		if(okey_sag)reverse(seg[x].s.begin(),seg[x].s.end());

		reverse(seg[b].f.begin(),seg[b].f.end());
		reverse(seg[b].s.begin(),seg[b].s.end());
	}

}


void bui(int x,int l,int r){
	if(l>r)return;
	if(l==r){
		seg[x]=arr[l];
		deg[x]=val[l];return;
	}
	int mid=(l+r)/2;
	bui(x*2,l,mid);bui(x*2+1,mid+1,r);
	deg[x]=query(l,r+1);
	if(deg[x]!=deg[x*2+1])yap(x,x*2+1,deg[x],1);
	if(deg[x]!=deg[x*2]) yap(x,x*2,deg[x],0);
	/*cout<<x<<" "<<l<<" "<<r<<": "<<deg[x]<<endl;

	for(auto u:seg[x].f)cout<<u<<" ";
	cout<<endl;
	for(auto u:seg[x].s)cout<<u<<" ";
	cout<<endl<<endl; */

}

void solve(int N){
	for(int i=1;i<N;i++){
		int de=query(i,i+1);
		arr[i]={{0,de},{de,0}};
		val[i]=de;
	}
	bui(1,1,N-1);
	int okey=0;
	for(auto u:seg[1].f){
		if(u==0){
			okey=1;break;
		}
		if(u==N-1)break;
	}
	if(okey){
		int i=1;
		for(auto u:seg[1].f){
			answer(i,u+1);
			i++;
		}
	}
	else{
		int i=1;
		for(auto u:seg[1].s){
			answer(i,u+1);
			i++;
		}
	}

}

/*signed main(){
	lalala;
	int n;cin>>n;
	solve(n);

}*/

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