Submission #831479

#TimeUsernameProblemLanguageResultExecution timeMemory
831479rainboyWatermelon (INOI20_watermelon)C11
49 / 100
48 ms17576 KiB
#include <stdio.h> #include <stdlib.h> #define N 100000 #define K 10 #define N_ (N * K + 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; } } 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 && 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:130:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d", &tt[i]);
      |   ^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...