oj.uz

Submission #635351

# Submission time Handle Problem Language Result Execution time Memory
635351 2022-08-26T06:32:50 Z S2speed Watermelon (INOI20_watermelon) C++17
0 / 100
 56 ms 14132 KB 
#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.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13896 KB Output is correct
2 Incorrect 56 ms 14132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13896 KB Output is correct
2 Incorrect 56 ms 14132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

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