oj.uz

Submission #947848

# Submission time Handle Problem Language Result Execution time Memory
947848 2024-03-17T06:29:21 Z PM1 Watermelon (INOI20_watermelon) C++17
0 / 100
 2000 ms 16208 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(a[n]!=n+1){
		cout<<-1;
		return 0;
	}
	//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;
		}
		for(auto i:state[mx]){
			tree.insert(i);
		}
		for(auto i:state[mx]){
			auto x=tree.upper_bound(i);
			if(x!=tree.end()){
				make(*x,i);
			}
			x=tree.lower_bound(i);
			if(x!=tree.begin()){
				x--;
				if(*x!=a[i])
					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

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 16208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 16208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -