Submission #1256609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256609		DangerNoodle7591	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	1016 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<<a<<endl;
	if(cevler[i]!=a)cout<<"a "<<i<<" "<<cevler[i]<<" "<<a<<endl;
	int of;
}*/

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

void yap(int x,int fark,int kim){
	vector<int> a[2],b[2];
	a[0]=seg[x*2],b[0]=seg[x*2+1];
	if(12){
		int mx=0;
		for(auto u:a[0]){
			mx=max(mx,u);
		}
		for(auto u:a[0])a[1].pb(mx-u);
		mx=0;
		for(auto u:b[0]){
			mx=max(mx,u);
		}
		for(auto u:b[0])b[1].pb(mx-u);
	}
	int ind=0;
	int yes=0;
	for(int i=0;i<2&&kim!=1;i++){
		for(int j=0;j<2;j++){
			if(seg[x].size())break;
			set<int> st;
			int mx=0,son=0;
			for(auto u:a[i]){
				mx=max(mx,u);
				son=u;
				st.ins(u);
			}
			int ok=1,okey=1;
			for(auto u:b[j]){
				if(ok){
					son-=u;
					ok=0;continue;
				}
				mx=max(mx,u+son);
				if(st.find(u+son)!=st.end()||u+son<0){okey=0;break;}
				//st.ins(u+son);
			}
			if(mx!=fark)okey=0;
			if(okey){
				for(auto u:a[i])seg[x].pb(u);
				ok=1;
				for(auto u:b[j]){
					if(ok){
						ok=0;continue;
					}
					seg[x].pb(u+son);
				}
			}
		}
	}
	for(int i=0;i<2&&kim!=2;i++){
		for(int j=0;j<2;j++){
			if(seg[x].size())break;
			set<int> st;
			int mx=0,son=-1;
			for(auto u:b[j]){
				mx=max(mx,u);
				if(son==-1)son=u;
				st.ins(u);
			}
			int ok=0,okey=1;
			//reverse(a[i].begin(),a[i].end());
			//if(a[i].size())
			if(a[i].size())son-=a[i][a[i].size()-1];
			for(auto u:a[i]){
				ok++;
				if(ok==a[i].size())break;

				mx=max(mx,u+son);
				if(st.find(u+son)!=st.end()||u+son<0){okey=0;break;}
				//st.ins(u+son);
			}
			if(mx!=fark)okey=0;
			if(okey){
				for(auto u:a[i])seg[x].pb(u+son);
				ok=1;
				for(auto u:b[j]){
					if(ok){
						ok=0;continue;
					}
					seg[x].pb(u);
				}
			}
		}
	}
}


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])yap(x,deg[x],2);
	else if(deg[x]==deg[x*2+1])yap(x,deg[x],1);
	else yap(x,deg[x],0);

	/*cout<<x<<" "<<l<<" "<<r+1<<": "<<deg[x]<<endl;
	for(int i=l;i<=r+1;i++){
		cout<<cevler[i]<<" ";
	}cout<<endl;
	for(auto u:seg[x])cout<<u<<" ";
	cout<<endl;*/

}

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

}

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

}*/

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