Submission #624247

#	Time	Username	Problem	Language	Result	Execution time	Memory
624247		Arinoor	Watermelon (INOI20_watermelon)	C++17	31 / 100	34 ms	8484 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int a[maxn], b[maxn], d[maxn];
int vis[maxn];
vector<int> G[maxn];
priority_queue<int, vector<int>, greater<int>> Q;

void dfs(int v){
	vis[v] = 1;
	for(int u : G[v]){
		if(!vis[u])
			dfs(u);
		else if(vis[u] == 1){
			cout << "-1\n";
			exit(0);
		}
	}
	vis[v] = 2;
}

int main(){
	ios;
	int n, k;
	cin >> n >> k;
	if(k > 1)
		return 0;
	for(int i = 1; i <= n; i ++){
		cin >> b[i];
	}
	if(~b[n])
		return cout << "-1\n", 0;
	vector<pii> S;
	for(int i = n; i; i --){
		if(b[i] == -1){
			if(!S.empty()){
				G[S.front().fi].pb(i);
				d[i] ++;
			}
			S.clear();
			S.pb(mp(i, inf));
		}
		else{
			pii last = mp(0, 0);
			while(S.back().se < b[i]){
				last = S.back();
				S.pop_back();
			}
			if(b[i] != last.se + 1)
				return cout << "-1\n", 0;
			if(last.fi){
				G[last.fi].pb(i);
				d[i] ++;
			}
			G[i].pb(S.back().fi);
			d[S.back().fi] ++;
			if(S.back().se == b[i]){
				S.pop_back();
			}
			S.pb(mp(i, b[i]));
		}
	}
	for(int i = 1; i <= n; i ++)
		if(!vis[i])
			dfs(i);
	for(int i = 1; i <= n; i ++)
		if(!d[i])
			Q.push(i);
	for(int i = 1; i <= n; i ++){
		int ind = Q.top();
		Q.pop();
		a[ind] = i;
		for(int u : G[ind])
			if(!(--d[u]))
				Q.push(u);
	}
	for(int i = 1; i <= n; i ++)
		cout << a[i] << ' ';
	cout << '\n';
}

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