Submission #813583

#	Time	Username	Problem	Language	Result	Execution time	Memory
813583		amirhoseinfar1385	Watermelon (INOI20_watermelon)	C++17	81 / 100	33 ms	8336 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int all[maxn],n,k,rishe=0,revcnt[maxn],link[maxn],res[maxn],cnt[maxn];
vector<int>par[maxn];
int vis[maxn],visind[maxn];
void cre(){
	for(int i=1;i<=n;i++){
		for(auto y:par[i]){
		//	cout<<i<<" "<<y<<"\n";
			revcnt[y]++;
		}
	//	cout<<i<<" "<<par[i]<<"\n";
	}
}

int aval(){
	vector<int>allv;
	vector<int>allcon;
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			allcon.push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		if(visind[i]==1){
			continue;
		}
		if(all[i]>=maxn){
			allv.push_back(i);
		}
	}
	int now=(int)allcon.size()-1;
	for(int i=0;i<(int)allv.size();i++){
		res[allv[i]]=allcon[now];
		now--;
	}
	now=0;
	int last=-1;
	vector<int>st;
	for(int j=1;j<=n;j++){
		if(all[j]==1){
			if(visind[j]==0){
				res[j]=allcon[now];
				now++;
			}
			int z=2;
			while((int)st.size()>0){
				auto x=st.back();
				if(all[x]==z){
					z++;
					if(visind[x]==0){
						res[x]=allcon[now];
						st.pop_back();
						now++;
					}
					continue;
				}
				break;
			}
		}	
		if(all[j]!=1&&all[j]<maxn){
			st.push_back(j);
		}
	}
	if((int)st.size()>0){
		//cout<<-1<<"\n";
	//	cout<<"wtf:\n";
	//	for(auto x:st){
	//		cout<<x<<'\n';
	//	}
		return -1;
	}
	for(int i=1;i<=n;i++){
		link[res[i]]=i;
	}
	return 1;
}

int bady(int l=0){
	if(k==0){
		return 1;
	}
	set<int>st;
	for(int j=n;j>l;j--){
		for(auto y:par[link[j]]){
			st.erase(y);
		}
		vector<int>tof;
		while((int)st.size()>0){
			auto x=*st.begin();
			st.erase(x);
			tof.push_back(x);
			//cout<<x<<" "<<j<<"\n";
			//cout<<x<<" "<<j<<" "<<res[x]<<" "<<res[link[j]]<<" "<<link[res[x]]<<" "<<link[j]<<"\n";
			int rx=res[x],rj=j;
			int lrx=link[res[x]],lj=link[j];
			res[lj]=rx;
			res[x]=rj;
			link[j]=lrx;
			link[rx]=lj;
			//swap(res[link[j]],res[x]);
			//swap(link[j],link[res[x]]);
			//cout<<x<<" "<<j<<" "<<res[x]<<" "<<res[link[j]]<<" "<<link[res[x]]<<" "<<link[res[j]]<<"\n";
			k--;
			visind[x]=1;
			vis[j]=1;
			aval();
			//cout<<k<<" salam\n";
			if(bady(j)==1){
				return 1;
			}
			//swap(res[link[j]],res[x]);
			//swap(link[j],link[res[x]]);	
			res[lj]=rj;
			res[x]=rx;
			link[j]=lj;
			link[rx]=lrx;
			visind[x]=vis[j]=0;
			aval();
		}
		for(auto x:tof){
			st.insert(x);
		}
		st.insert(link[j]);
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	if(all[n]!=-1){
		cout<<-1<<"\n";
		return 0;
	}
	vector<int>fake;
	for(int i=1;i<=n;i++){
		if(all[i]==-1){
			fake.push_back(i);
		}
	}
	for(int i=0;i<(int)fake.size();i++){
		all[fake[i]]=maxn*2-i;
	}	
	rishe=fake[0];
	vector<int>v;
	for(int i=n;i>=1;i--){
		while((int)v.size()>0&&all[v.back()]<all[i]){
			v.pop_back();
		}
		if((int)v.size()!=0){
		//	cout<<i<<" "<<v.back()<<"\n";
			par[i].push_back(v.back());
		}
		v.push_back(i);
	}
	v.clear();
	for(int i=1;i<=n;i++){
		while((int)v.size()>0&&all[v.back()]<all[i]){
			v.pop_back();
		}
		if((int)v.size()!=0&&all[v.back()]>all[i]){
			par[i].push_back(v.back());
		}
		while((int)v.size()>0&&all[v.back()]<=all[i]){
			v.pop_back();
		}
		v.push_back(i);
	}
	//cre();
	//cout<<"salam"<<endl;
	if(aval()==-1){
		//cout<<"ha"<<endl;
		cout<<-1<<'\n';
		return 0;
	}
//	cout<<"salam"<<endl;
	k--;
	if(bady()==-1){
		cout<<-1<<"\n";
		return 0;
	}
	for(int i=1;i<=n;i++){
		res[link[i]]=i;
	}
	for(int i=1;i<=n;i++){
		cout<<res[i]<<" ";
	}
}

// 3 2 1 1 2 3 4 3 2 1 -1

Compilation message (stderr)

Main.cpp: In function 'int aval()':
Main.cpp:39:6: warning: unused variable 'last' [-Wunused-variable]
   39 |  int last=-1;
      |      ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 18 / 18
• Subtask 5: 0 / 19