Submission #948228

# Submission time Handle Problem Language Result Execution time Memory
948228 2024-03-17T23:57:44 Z amirhoseinfar1385 Watermelon (INOI20_watermelon) C++17
0 / 100
25 ms 12892 KB
#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){
	mark[z]=1;
	sz[z]=v[z].size();
	for(auto i:v[z]){
		if(!mark[i])
			dfs(i);
	}
	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]++;
			s.erase(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]);
		}
	}
	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;
		}
		for(auto i:state[mx]){
			tree.insert(i);
		}
		for(auto i:state[mx]){
			auto x=tree.upper_bound(i);
			if(x!=tree.end()){
			  int wtf=*x;
			  int f=0;
			  for(int j=i;j<wtf;j++){
			    if(a[j]==mx-1){
			      f=1;
			    }
			  }
			  if(f==0){
			    cout<<-1<<"\n";
			    exit(0);
			  }
				make(*x,i);
			}
			x=tree.lower_bound(i);
			if(x!=tree.begin()){
				x--;
				if(*x!=a[i])
					make(*x,i);
			}
			
		}
		mx--;
	}
	for(int i=1;i<=n;i++){
		if(a[i]==n+1 || a[i]==1)continue;
		bool rrr=0;
		for(auto j:v[i]){
			//cout<<j<<" ";
			if(j==a[i]-1)rrr=1;
		}//cout<<'\n';
		if(!rrr){
			cout<<-1;
			return 0;
		}
	}
	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

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++){
      |              ~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -