Submission #946528

#	Time	Username	Problem	Language	Result	Execution time	Memory
946528		PM1	Watermelon (INOI20_watermelon)	C++17	0 / 100	2050 ms	14868 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e5+5;
int n,k,a[mxn],ans=0,res[mxn],mx,dis[mxn],sz[mxn];
vector<int>v[mxn],state[mxn],par[mxn];
set<int>s;
set<int>tree;
bool mark[mxn];
void dfs(int z){
	//cout<<z<<" ";
	for(auto i:v[z]){
			dfs(i);
			sz[z]++;
	}
	if(!v[z].size())s.insert(z);
}
void solve(int x=1){
	if(x==n+1){
		ans++;
		return;
	}
	auto y=s.upper_bound(0);
	while(y!=s.end()){
		int z=*y;
		s.erase(z);

		for(auto j:par[z]){
			sz[j]--;
			if(!sz[j])
				s.insert(j);
		}
		
		solve(x+1);
		s.insert(z);

		for(auto j:par[z]){
			sz[j]++;
			if(sz[j])
				s.insert(j);
		}

		if(ans==k){
			res[z]=x;
			break;
		}
		y=s.upper_bound(z);
	}
}
void make(int x,int y){
	//cout<<x<<" "<<y<<'\n';
	par[y].push_back(x);
	tree.insert(x);
	tree.insert(y);
	v[x].push_back(y);
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==-1){
			state[n+1].push_back(i);
			a[i]=n+1;
		}
		else{
			state[a[i]].push_back(i);
			mx=max(mx,a[i]);
		}
	}
	//assert(state[n+1].size());
	if (!state[n+1].size() || state[n+1].back()!=n){
		cout<<-1;
		return 0;
	}
	for(int i=1;i<state[n+1].size();i++){
		make(state[n+1][i-1],state[n+1][i]);
	}
	tree.insert(state[n+1][0]);
	while(mx){
		if(state[mx].size()==0){
			cout<<-1;
			return 0;
		}
		reverse(state[mx].begin(),state[mx].end());
		for(auto i:state[mx]){
			auto x=tree.lower_bound(i);
			if(x!=tree.begin()){
				x--;
				make(*x,i);
			}
			x=tree.upper_bound(i);
			if(x!=tree.end()){
				make(*x,i);
			}
			
		}
		mx--;
	}

	dfs(state[n+1][0]);
	solve();
	if(ans<k){
		cout<<-1;
	}
	else{
		for(int i=1;i<=n;i++){
			cout<<res[i]<<" ";
		}
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i=1;i<state[n+1].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~

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