Submission #635351

#	Time	Username	Problem	Language	Result	Execution time	Memory
635351		S2speed	Watermelon (INOI20_watermelon)	C++17	0 / 100	56 ms	14132 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define sze(x) (int)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;

const ll maxn = 1e5 + 17 , inf = 2e8;

ll a[maxn] , p[maxn] , b[maxn] , d[maxn] , f[maxn] , ans[maxn];
vector<ll> adj[maxn] , jda[maxn] , v;
set<pll> s;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n , k;
	cin>>n>>k;
	for(ll i = 0 ; i < n ; i++){
		cin>>a[i];
	}
	if(a[n - 1] != -1){
		cout<<"-1\n";
		return 0;
	}
	ll o = n + 1;
	for(ll i = n - 1 ; ~i ; i--){
		if(a[i] == -1){
			a[i] = o++;
		}
	}
	for(ll i = n - 1 ; ~i ; i--){
		while(!v.empty()){
			ll j = v.back();
			if(a[j] >= a[i]) break;
			adj[i].push_back(j); jda[j].push_back(i);
			d[i]++;
			v.pop_back();
		}
		if(!v.empty()){
			adj[v.back()].push_back(i); jda[i].push_back(v.back());
			d[v.back()]++;
			if(a[v.back()] == a[i]) v.pop_back();
		}
		v.push_back(i);
	}
	for(ll e = 0 ; e < k ; e++){
		if(b[0] == -1){
			cout<<"-1\n";
			return 0;
		}
		memcpy(f , d , sizeof(f));
		for(ll i = 0 ; i < n ; i++){
			s.insert({f[i] , i});
		}
		ll ind = -1;
		for(ll i = 0 ; i < n ; i++){
			auto it = s.begin();
			ll h = b[i];
			while(h--){
				it++;
			}
			p[i] = (*it).second;
			it++;
			if(it != s.end()){
				if((*it).first == 0){
					ind = i;
				}
			}
			s.erase(--it);
			ll v = p[i];
			for(auto j : jda[v]){
				s.erase({f[j] , j});
				s.insert({--f[j] , j});
			}
		}
		if(ind == -1){
			b[0] = -1;
		} else {
			b[ind]++;
			for(ll j = ind + 1 ; j < n ; j++) b[j] = 0;
		}
	}
	for(ll i = 0 ; i < n ; i++){
		ans[p[i]] = i + 1;
//		cout<<p[i]<<' ';
	}
//	cout<<'\n';
	for(ll i = 0 ; i < n ; i++){
		cout<<ans[i]<<' ';
	}
	cout<<'\n';
	return 0;
}

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