Submission #813578

#	Time	Username	Problem	Language	Result	Execution time	Memory
813578		amirhoseinfar1385	Watermelon (INOI20_watermelon)	C++17	31 / 100	21 ms	8696 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];
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;
	for(int i=1;i<=n;i++){
		if(all[i]>=maxn){
			allv.push_back(i);
		}
	}
	vector<int>w(n+1);
	int now=n;
	for(int i=0;i<(int)allv.size();i++){
		res[allv[i]]=now;
		w[now]=i;
		now--;
	}
	now=1;
	int last=-1;
	vector<int>st;
	for(int j=1;j<=n;j++){
		if(all[j]==1){
			res[j]=now;
			now++;
			int z=2;
			while((int)st.size()>0){
				auto x=st.back();
				if(all[x]==z){
					z++;
					res[x]=now;
					w[now]=x;
					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";
		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);
		}
		if((int)st.size()>0){
			auto x=*st.begin();
			//cout<<x<<" "<<j<<"\n";
			//cout<<x<<" "<<j<<" "<<res[x]<<" "<<res[link[j]]<<" "<<link[res[x]]<<" "<<link[j]<<"\n";
			int rx=res[x],rj=res[link[j]];
			int lrx=link[res[x]],lj=link[j];
			res[link[j]]=rx;
			res[x]=rj;
			link[j]=lrx;
			link[res[x]]=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--;
			//cout<<k<<" salam\n";
			if(bady(j)==1){
				return 1;
			}
			//swap(res[link[j]],res[x]);
			//swap(link[j],link[res[x]]);	
			res[link[j]]=rj;
			res[x]=rx;
			link[res[x]]=lrx;
			link[j]=lj;
		}
		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;
	}
	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:31:6: warning: unused variable 'last' [-Wunused-variable]
   31 |  int last=-1;
      |      ^~~~

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