Submission #946513

#	Time	Username	Problem	Language	Result	Execution time	Memory
946513		PM1	Watermelon (INOI20_watermelon)	C++17	0 / 100	42 ms	17364 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],par[mxn],ans=0,res[mxn],mx,dis[mxn],sz[mxn];
vector<int>v[mxn],state[mxn];
set<int>s;
set<pair<int,int>>tree;
bool mark[mxn];
void dfs(int z){
	bool cnt=0;
	for(auto i:v[z]){
		if(par[z]!=i){
			cnt=1;
			dfs(i);
			sz[z]++;
		}
	}
	if(!cnt)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);
		sz[par[z]]--;
		if(!sz[par[z]])
			s.insert(par[z]);
		solve(x+1);
		s.insert(z);
		sz[par[z]]++;
		if(sz[par[z]])
			s.erase(par[z]);
		y=s.upper_bound(z);
		if(ans==k){
			res[z]=x;
			break;
		}
	}
}
void make(int x,int y){
	//cout<<x<<" "<<y<<'\n';
	par[y]=x;
	tree.insert({x,a[x]});
	tree.insert({y,a[y]});
	v[x].push_back(y);
	v[y].push_back(x);
}
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()){
		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],n+1});
	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(make_pair(i,0));
			if(x==tree.end()){
				x--;
				make(x->fr,i);
				continue;
			}
			if(x==tree.begin()){
				make(x->fr,i);
				continue;
			}
			auto y=x;
			y--;
			if(x->sc>y->sc)
				make(y->fr,i);
			else if(x->sc<y->sc)
				make(x->fr,i);
			else{
				if(y->sc==n+1)
					make(x->fr,i);
				else
					make(y->fr,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:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  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