Submission #624249

#	Time	Username	Problem	Language	Result	Execution time	Memory
624249		Arinoor	Watermelon (INOI20_watermelon)	C++17	100 / 100	145 ms	9656 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 maxlg = 17;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int n, a[maxn], b[maxn], d[maxn], D[maxn], t[maxn];
int vis[maxn];
int fen[maxn];
vector<int> G[maxn];

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;
}

void add(int i, int x){
	for(; i <= n; i += i & -i)
		fen[i] += x;
}

int get(int t){
	int x = 0;
	for(int i = maxlg - 1; ~i; i --){
		int j = x + (1 << i);
		if(j <= n and fen[j] < t){
			x = j;
			t -= fen[j];
		}
	}
	return x + 1;
}

int main(){
	ios;
	int k;
	cin >> n >> k;
	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 ++)
		t[i] = 1;
	for(int i = 1; i <= k; i ++){
		memset(fen, 0, sizeof fen);
		int last = 0, cnt = 0;
		for(int i = 1; i <= n; i ++){
			D[i] = d[i];
			if(!D[i]){
				add(i, 1);
				cnt ++;
			}
		}
		for(int j = 1; j <= n; j ++){
			int x = get(t[j]);
			if(cnt > t[j])
				last = j;
			add(x, -1);
			cnt --;
			a[x] = j;
			for(int u : G[x]){
				if(!(--D[u])){
					add(u, 1);
					cnt ++;
				}
			}
		}
		if(i == k){
			for(int j = 1; j <= n; j ++)
				cout << a[j] << ' ';
			return cout << '\n', 0;
		}
		if(!last)
			return cout << "-1\n", 0;
		t[last] ++;
		for(int j = last + 1; j <= n; j ++)
			t[j] = 1;
	}
}

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