Submission #831491

#	Time	Username	Problem	Language	Result	Execution time	Memory
831491		rainboy	Watermelon (INOI20_watermelon)	C11	100 / 100	53 ms	29728 KiB

Main

#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define K	10
#define N_	(N * K * 2 + 1)

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int n, k;

int *ej[N], eo[N], dd[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j, dd[j]++;
}

int zz[N_], ll[N_], rr[N_], ii[N_], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = i;
	return _++;
}

void split(int u, int i) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (ii[u] < i) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (ii[u] > i) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

void tr_add(int i) {
	split(u_, i);
	u_ = merge(merge(l_, node(i)), r_);
}

void tr_remove(int i) {
	split(u_, i);
	u_ = merge(l_, r_);
}

int tr_higher(int i) {
	int u = u_, i_ = -1;

	while (u)
		if (ii[u] > i)
			i_ = ii[u], u = ll[u];
		else
			u = rr[u];
	return i_;
}

int aa[N];

int branch(int a) {
	int i, o;

	if (a == n) {
		if (--k == 0) {
			for (i = 0; i < n; i++)
				printf("%d ", aa[i] + 1);
			printf("\n");
			return 1;
		}
		return 0;
	}
	if (u_ == 0)
		return 0;
	i = -1;
	while ((i = tr_higher(i)) != -1) {
		tr_remove(i);
		aa[i] = a;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (--dd[j] == 0)
				tr_add(j);
		}
		if (branch(a + 1))
			return 1;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (dd[j]++ == 0)
				tr_remove(j);
		}
		tr_add(i);
	}
	return 0;
}

int main() {
	static int tt[N], qu[N];
	int cnt, h, i;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &tt[i]);
	if (tt[n - 1] != -1) {
		printf("-1\n");
		return 0;
	}
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	cnt = 0;
	for (i = n - 1; i >= 0; i--)
		if (tt[i] == -1) {
			while (cnt)
				append(qu[--cnt], i);
			qu[cnt++] = i;
		} else {
			h = cnt;
			while (h >= 2 && tt[qu[h - 1]] < tt[i])
				append(qu[--h], i);
			if ((h == cnt ? 0 : tt[qu[h]]) != tt[i] - 1) {
				printf("-1\n");
				return 0;
			}
			append(i, qu[h - 1]);
			if (h >= 2 && tt[qu[h - 1]] == tt[i])
				h--;
			qu[h++] = i;
			cnt = h;
		}
	for (i = 0; i < n; i++)
		if (dd[i] == 0)
			tr_add(i);
	if (!branch(0))
		printf("-1\n");
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:131:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:133:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   scanf("%d", &tt[i]);
      |   ^~~~~~~~~~~~~~~~~~~

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