#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
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 time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
288 KB |
Output is correct |
3 |
Correct |
1 ms |
292 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Incorrect |
1 ms |
284 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
288 KB |
Output is correct |
3 |
Correct |
1 ms |
292 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Incorrect |
1 ms |
284 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
8144 KB |
Output is correct |
2 |
Correct |
5 ms |
2724 KB |
Output is correct |
3 |
Correct |
18 ms |
8144 KB |
Output is correct |
4 |
Correct |
5 ms |
2644 KB |
Output is correct |
5 |
Correct |
18 ms |
8056 KB |
Output is correct |
6 |
Correct |
19 ms |
8068 KB |
Output is correct |
7 |
Correct |
20 ms |
8104 KB |
Output is correct |
8 |
Correct |
23 ms |
8140 KB |
Output is correct |
9 |
Correct |
27 ms |
8096 KB |
Output is correct |
10 |
Correct |
22 ms |
8140 KB |
Output is correct |
11 |
Correct |
38 ms |
15924 KB |
Output is correct |
12 |
Correct |
38 ms |
15856 KB |
Output is correct |
13 |
Correct |
37 ms |
15908 KB |
Output is correct |
14 |
Correct |
39 ms |
15868 KB |
Output is correct |
15 |
Correct |
9 ms |
5040 KB |
Output is correct |
16 |
Correct |
11 ms |
5152 KB |
Output is correct |
17 |
Correct |
15 ms |
5076 KB |
Output is correct |
18 |
Correct |
14 ms |
5092 KB |
Output is correct |
19 |
Correct |
9 ms |
5092 KB |
Output is correct |
20 |
Correct |
10 ms |
5016 KB |
Output is correct |
21 |
Correct |
14 ms |
5112 KB |
Output is correct |
22 |
Correct |
11 ms |
5104 KB |
Output is correct |
23 |
Correct |
10 ms |
5064 KB |
Output is correct |
24 |
Correct |
26 ms |
16256 KB |
Output is correct |
25 |
Correct |
26 ms |
16248 KB |
Output is correct |
26 |
Correct |
27 ms |
16160 KB |
Output is correct |
27 |
Correct |
26 ms |
16204 KB |
Output is correct |
28 |
Correct |
26 ms |
16276 KB |
Output is correct |
29 |
Correct |
26 ms |
16204 KB |
Output is correct |
30 |
Correct |
8 ms |
5076 KB |
Output is correct |
31 |
Correct |
19 ms |
8140 KB |
Output is correct |
32 |
Correct |
26 ms |
14444 KB |
Output is correct |
33 |
Correct |
27 ms |
16112 KB |
Output is correct |
34 |
Correct |
4 ms |
1876 KB |
Output is correct |
35 |
Correct |
5 ms |
3412 KB |
Output is correct |
36 |
Correct |
13 ms |
8148 KB |
Output is correct |
37 |
Correct |
32 ms |
15972 KB |
Output is correct |
38 |
Correct |
32 ms |
15940 KB |
Output is correct |
39 |
Correct |
27 ms |
16120 KB |
Output is correct |
40 |
Correct |
31 ms |
15900 KB |
Output is correct |
41 |
Correct |
28 ms |
16332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
8144 KB |
Output is correct |
2 |
Correct |
5 ms |
2724 KB |
Output is correct |
3 |
Correct |
18 ms |
8144 KB |
Output is correct |
4 |
Correct |
5 ms |
2644 KB |
Output is correct |
5 |
Correct |
18 ms |
8056 KB |
Output is correct |
6 |
Correct |
19 ms |
8068 KB |
Output is correct |
7 |
Correct |
20 ms |
8104 KB |
Output is correct |
8 |
Correct |
23 ms |
8140 KB |
Output is correct |
9 |
Correct |
27 ms |
8096 KB |
Output is correct |
10 |
Correct |
22 ms |
8140 KB |
Output is correct |
11 |
Correct |
38 ms |
15924 KB |
Output is correct |
12 |
Correct |
38 ms |
15856 KB |
Output is correct |
13 |
Correct |
37 ms |
15908 KB |
Output is correct |
14 |
Correct |
39 ms |
15868 KB |
Output is correct |
15 |
Correct |
9 ms |
5040 KB |
Output is correct |
16 |
Correct |
11 ms |
5152 KB |
Output is correct |
17 |
Correct |
15 ms |
5076 KB |
Output is correct |
18 |
Correct |
14 ms |
5092 KB |
Output is correct |
19 |
Correct |
9 ms |
5092 KB |
Output is correct |
20 |
Correct |
10 ms |
5016 KB |
Output is correct |
21 |
Correct |
14 ms |
5112 KB |
Output is correct |
22 |
Correct |
11 ms |
5104 KB |
Output is correct |
23 |
Correct |
10 ms |
5064 KB |
Output is correct |
24 |
Correct |
26 ms |
16256 KB |
Output is correct |
25 |
Correct |
26 ms |
16248 KB |
Output is correct |
26 |
Correct |
27 ms |
16160 KB |
Output is correct |
27 |
Correct |
26 ms |
16204 KB |
Output is correct |
28 |
Correct |
26 ms |
16276 KB |
Output is correct |
29 |
Correct |
26 ms |
16204 KB |
Output is correct |
30 |
Correct |
8 ms |
5076 KB |
Output is correct |
31 |
Correct |
19 ms |
8140 KB |
Output is correct |
32 |
Correct |
26 ms |
14444 KB |
Output is correct |
33 |
Correct |
27 ms |
16112 KB |
Output is correct |
34 |
Correct |
4 ms |
1876 KB |
Output is correct |
35 |
Correct |
5 ms |
3412 KB |
Output is correct |
36 |
Correct |
13 ms |
8148 KB |
Output is correct |
37 |
Correct |
32 ms |
15972 KB |
Output is correct |
38 |
Correct |
32 ms |
15940 KB |
Output is correct |
39 |
Correct |
27 ms |
16120 KB |
Output is correct |
40 |
Correct |
31 ms |
15900 KB |
Output is correct |
41 |
Correct |
28 ms |
16332 KB |
Output is correct |
42 |
Correct |
18 ms |
8100 KB |
Output is correct |
43 |
Correct |
5 ms |
2740 KB |
Output is correct |
44 |
Correct |
18 ms |
8092 KB |
Output is correct |
45 |
Correct |
5 ms |
2716 KB |
Output is correct |
46 |
Correct |
5 ms |
2644 KB |
Output is correct |
47 |
Correct |
5 ms |
2740 KB |
Output is correct |
48 |
Correct |
5 ms |
2644 KB |
Output is correct |
49 |
Correct |
18 ms |
8144 KB |
Output is correct |
50 |
Correct |
21 ms |
8132 KB |
Output is correct |
51 |
Correct |
18 ms |
8104 KB |
Output is correct |
52 |
Correct |
38 ms |
15936 KB |
Output is correct |
53 |
Correct |
48 ms |
15896 KB |
Output is correct |
54 |
Correct |
9 ms |
5132 KB |
Output is correct |
55 |
Correct |
13 ms |
5108 KB |
Output is correct |
56 |
Correct |
26 ms |
14528 KB |
Output is correct |
57 |
Correct |
36 ms |
15980 KB |
Output is correct |
58 |
Correct |
32 ms |
16068 KB |
Output is correct |
59 |
Correct |
34 ms |
16288 KB |
Output is correct |
60 |
Correct |
27 ms |
16168 KB |
Output is correct |
61 |
Correct |
33 ms |
17576 KB |
Output is correct |
62 |
Correct |
22 ms |
17224 KB |
Output is correct |
63 |
Correct |
26 ms |
16380 KB |
Output is correct |
64 |
Correct |
25 ms |
16428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
288 KB |
Output is correct |
3 |
Correct |
1 ms |
292 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Incorrect |
1 ms |
284 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |