Submission #813546

#	Time	Username	Problem	Language	Result	Execution time	Memory
813546		amirhoseinfar1385	Watermelon (INOI20_watermelon)	C++17	0 / 100	18 ms	6268 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(){
	cre();
	set<int>st;
	for(int i=1;i<=n;i++){
		if(revcnt[i]==0){
			st.insert(i);
		}
	}
	int ted=0;
	while((int)st.size()>0){
		ted++;
		auto x=*st.begin();
		st.erase(x);
		res[x]=ted;
		link[ted]=x;
		for(auto y:par[x]){
			revcnt[y]--;
			if(y!=0&&revcnt[y]==0){
				st.insert(y);
			}
		}
		//cout<<ted<<" "<<x<<" "<<(int)st.size()<<" "<<revcnt[par[x]]<<"\n";
	}
	if(ted!=n){
		return -1;
	}
	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<<" "<<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--;
			if(bady(j)!=1){
				return 1;
			}
			swap(res[link[j]],res[x]);
			swap(link[j],link[res[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);
	}
	//cout<<"salam"<<endl;
	if(aval()==-1){
		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]<<" ";
	}
}

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