oj.uz

Submission #1101137

# Submission time Handle Problem Language Result Execution time Memory
1101137 2024-10-15T15:23:59 Z rainboy Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 448 ms 1536 KB 
#include "sphinx.h"
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

typedef vector<int> vi;

const int N = 250, M = N * (N - 1) / 2;

int n, m;
int *ej[N], eo[N], ii[M], jj[M];

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


int cc[N], iii[2][N], nn[2], nn_[2];

void dfs(int i, int c) {
	if (cc[i] != -1)
		return;
	cc[i] = c, iii[c][nn[c]++] = i;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		dfs(j, c ^ 1);
	}
}

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

int query(vi aa, int a) {
	int k = perform_experiment(aa);
	memset(ds, -1, n * sizeof *ds);
	for (int h = 0; h < m; h++) {
		int i = ii[h], j = jj[h];
		if (aa[i] == aa[j])
			join(i, j);
	}
	for (int i = 0; i < n; i++)
		if (ds[i] < 0 && (aa[i] == n || aa[i] == a))
			k--;
	return k;
}

int ii1[N], n1;
char first[N];

vi find_colours(int n_, vi ii_, vi jj_) {
	n = n_, m = ii_.size();
	for (int h = 0; h < m; h++)
		ii[h] = ii_[h], jj[h] = jj_[h];
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (int h = 0; h < m; h++) {
		int i = ii[h], j = jj[h];
		append(i, j), append(j, i);
	}
	memset(cc, -1, n * sizeof *cc), dfs(0, 0);
	vi aa(n, -2);
	for (int c = 0; c < 2; c++) {
		vi bb(n, n);
		memset(first, 0, n * sizeof *first);
		n1 = 0;
		for (int h = 0, k = 0; h < nn[c]; h++) {
			int i = iii[c][h];
			bb[i] = -1;
			if (query(bb, -2) == k + 1)
				first[i] = 1, ii1[n1++] = i, k++;
			else
				bb[i] = n;
		}
		for (int a = 0; a < n; a++) {
			for (int i = 0; i < n; i++)
				bb[i] = a;
			for (int h = 0; h < nn[c]; h++)
				bb[iii[c][h]] = n;
			for (int h = 0; h < n1; h++)
				bb[ii1[h]] = -1;
			int lower = 0, upper = n1, kl = 0, kr = upper - query(bb, a);
			while (kl != kr) {
				int upper = n1, kl_ = kr;
				while (upper - lower > 1) {
					int n_ = (lower + upper) / 2;
					for (int i = 0; i < n; i++)
						bb[i] = a;
					for (int h = 0; h < nn[c]; h++)
						bb[iii[c][h]] = n;
					for (int h = 0; h < n_; h++)
						bb[ii1[h]] = -1;
					int k = n_ - query(bb, a);
					if (k == kl)
						lower = n_;
					else
						upper = n_, kl_ = k;
				}
				aa[ii1[lower]] = a;
				lower = upper, kl = kl_;
			}
		}
		for (int h = 0; h < nn[c]; h++) {
			int i_ = iii[c][h];
			if (!first[i_]) {
				n1 = 0;
				for (int o = eo[i_]; o--; ) {
					int j = ej[i_][o];
					if (first[j])
						ii1[n1++] = j;
				}
				int lower = 0, upper = n1;
				while (upper - lower > 1) {
					int n_ = (lower + upper) / 2;
					for (int i = 0; i < n; i++)
						bb[i] = n;
					bb[i_] = -1;
					for (int h = 0; h < n_; h++)
						bb[ii1[h]] = -1;
					if (query(bb, -2) == n_ + 1)
						lower = n_;
					else
						upper = n_;
				}
				aa[i_] = aa[ii1[lower]];
			}
		}
	}
  return aa;
}

Compilation message

sphinx.cpp: In function 'void append(int, int)':
sphinx.cpp:17:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB #experiments: 15

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 6
2 Correct 1 ms 336 KB #experiments: 6
3 Correct 1 ms 336 KB #experiments: 6
4 Correct 1 ms 336 KB #experiments: 6

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB #experiments: 15
2 Correct 1 ms 336 KB #experiments: 6
3 Correct 1 ms 336 KB #experiments: 6
4 Correct 1 ms 336 KB #experiments: 6
5 Correct 1 ms 336 KB #experiments: 6
6 Correct 3 ms 504 KB #experiments: 298
7 Correct 3 ms 336 KB #experiments: 298
8 Correct 4 ms 336 KB #experiments: 303
9 Correct 4 ms 336 KB #experiments: 309
10 Correct 5 ms 512 KB #experiments: 317
11 Correct 3 ms 336 KB #experiments: 330
12 Correct 5 ms 336 KB #experiments: 379
13 Correct 6 ms 336 KB #experiments: 386
14 Correct 2 ms 336 KB #experiments: 150
15 Correct 5 ms 336 KB #experiments: 266
16 Correct 6 ms 504 KB #experiments: 291
17 Correct 5 ms 512 KB #experiments: 298
18 Correct 7 ms 336 KB #experiments: 350
19 Correct 5 ms 336 KB #experiments: 355
20 Correct 6 ms 512 KB #experiments: 370
21 Correct 5 ms 336 KB #experiments: 386
22 Correct 6 ms 336 KB #experiments: 339
23 Correct 6 ms 336 KB #experiments: 336
24 Correct 7 ms 336 KB #experiments: 339
25 Correct 7 ms 336 KB #experiments: 374
26 Correct 5 ms 336 KB #experiments: 320
27 Correct 6 ms 336 KB #experiments: 350
28 Correct 4 ms 336 KB #experiments: 379
29 Correct 4 ms 336 KB #experiments: 308
30 Correct 7 ms 336 KB #experiments: 357
31 Correct 5 ms 336 KB #experiments: 312
32 Correct 8 ms 336 KB #experiments: 362
33 Correct 3 ms 336 KB #experiments: 195
34 Correct 6 ms 336 KB #experiments: 386

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 6
2 Correct 1 ms 336 KB #experiments: 6
3 Correct 1 ms 336 KB #experiments: 6
4 Correct 1 ms 336 KB #experiments: 6
5 Correct 3 ms 504 KB #experiments: 298
6 Correct 3 ms 336 KB #experiments: 298
7 Correct 4 ms 336 KB #experiments: 303
8 Correct 4 ms 336 KB #experiments: 309
9 Correct 5 ms 512 KB #experiments: 317
10 Correct 3 ms 336 KB #experiments: 330
11 Correct 5 ms 336 KB #experiments: 379
12 Correct 6 ms 336 KB #experiments: 386
13 Correct 50 ms 336 KB #experiments: 2014
14 Correct 43 ms 336 KB #experiments: 2024
15 Correct 53 ms 512 KB #experiments: 2034
16 Correct 57 ms 348 KB #experiments: 2070
17 Correct 52 ms 336 KB #experiments: 2161
18 Correct 43 ms 336 KB #experiments: 2293
19 Correct 58 ms 336 KB #experiments: 2436
20 Correct 48 ms 508 KB #experiments: 2010
21 Correct 76 ms 336 KB #experiments: 2494

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 6
2 Correct 1 ms 336 KB #experiments: 6
3 Correct 1 ms 336 KB #experiments: 6
4 Correct 1 ms 336 KB #experiments: 6
5 Correct 2 ms 336 KB #experiments: 150
6 Correct 5 ms 336 KB #experiments: 266
7 Correct 6 ms 504 KB #experiments: 291
8 Correct 5 ms 512 KB #experiments: 298
9 Correct 7 ms 336 KB #experiments: 350
10 Correct 5 ms 336 KB #experiments: 355
11 Correct 6 ms 512 KB #experiments: 370
12 Correct 5 ms 336 KB #experiments: 386
13 Correct 158 ms 1372 KB #experiments: 1000
14 Correct 208 ms 1360 KB #experiments: 1418
15 Correct 286 ms 1360 KB #experiments: 1733
16 Correct 279 ms 1536 KB #experiments: 1973
17 Correct 275 ms 1360 KB #experiments: 2232
18 Correct 250 ms 1360 KB #experiments: 2385
19 Correct 264 ms 1360 KB #experiments: 2427
20 Correct 95 ms 1360 KB #experiments: 750
21 Correct 276 ms 1360 KB #experiments: 2494

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB #experiments: 15
2 Correct 1 ms 336 KB #experiments: 6
3 Correct 1 ms 336 KB #experiments: 6
4 Correct 1 ms 336 KB #experiments: 6
5 Correct 1 ms 336 KB #experiments: 6
6 Correct 3 ms 504 KB #experiments: 298
7 Correct 3 ms 336 KB #experiments: 298
8 Correct 4 ms 336 KB #experiments: 303
9 Correct 4 ms 336 KB #experiments: 309
10 Correct 5 ms 512 KB #experiments: 317
11 Correct 3 ms 336 KB #experiments: 330
12 Correct 5 ms 336 KB #experiments: 379
13 Correct 6 ms 336 KB #experiments: 386
14 Correct 2 ms 336 KB #experiments: 150
15 Correct 5 ms 336 KB #experiments: 266
16 Correct 6 ms 504 KB #experiments: 291
17 Correct 5 ms 512 KB #experiments: 298
18 Correct 7 ms 336 KB #experiments: 350
19 Correct 5 ms 336 KB #experiments: 355
20 Correct 6 ms 512 KB #experiments: 370
21 Correct 5 ms 336 KB #experiments: 386
22 Correct 6 ms 336 KB #experiments: 339
23 Correct 6 ms 336 KB #experiments: 336
24 Correct 7 ms 336 KB #experiments: 339
25 Correct 7 ms 336 KB #experiments: 374
26 Correct 5 ms 336 KB #experiments: 320
27 Correct 6 ms 336 KB #experiments: 350
28 Correct 4 ms 336 KB #experiments: 379
29 Correct 4 ms 336 KB #experiments: 308
30 Correct 7 ms 336 KB #experiments: 357
31 Correct 5 ms 336 KB #experiments: 312
32 Correct 8 ms 336 KB #experiments: 362
33 Correct 3 ms 336 KB #experiments: 195
34 Correct 6 ms 336 KB #experiments: 386
35 Correct 50 ms 336 KB #experiments: 2014
36 Correct 43 ms 336 KB #experiments: 2024
37 Correct 53 ms 512 KB #experiments: 2034
38 Correct 57 ms 348 KB #experiments: 2070
39 Correct 52 ms 336 KB #experiments: 2161
40 Correct 43 ms 336 KB #experiments: 2293
41 Correct 58 ms 336 KB #experiments: 2436
42 Correct 48 ms 508 KB #experiments: 2010
43 Correct 76 ms 336 KB #experiments: 2494
44 Correct 158 ms 1372 KB #experiments: 1000
45 Correct 208 ms 1360 KB #experiments: 1418
46 Correct 286 ms 1360 KB #experiments: 1733
47 Correct 279 ms 1536 KB #experiments: 1973
48 Correct 275 ms 1360 KB #experiments: 2232
49 Correct 250 ms 1360 KB #experiments: 2385
50 Correct 264 ms 1360 KB #experiments: 2427
51 Correct 95 ms 1360 KB #experiments: 750
52 Correct 276 ms 1360 KB #experiments: 2494
53 Correct 63 ms 336 KB #experiments: 1969
54 Correct 78 ms 336 KB #experiments: 1981
55 Correct 78 ms 592 KB #experiments: 1911
56 Correct 92 ms 764 KB #experiments: 1823
57 Correct 210 ms 848 KB #experiments: 2206
58 Correct 188 ms 848 KB #experiments: 2279
59 Correct 172 ms 848 KB #experiments: 2198
60 Correct 234 ms 848 KB #experiments: 2443
61 Correct 47 ms 336 KB #experiments: 2156
62 Correct 58 ms 336 KB #experiments: 2331
63 Correct 63 ms 504 KB #experiments: 2440
64 Correct 60 ms 336 KB #experiments: 1947
65 Correct 69 ms 336 KB #experiments: 1986
66 Correct 67 ms 592 KB #experiments: 1967
67 Correct 70 ms 592 KB #experiments: 2021
68 Correct 87 ms 592 KB #experiments: 1938
69 Correct 68 ms 592 KB #experiments: 1938
70 Correct 67 ms 592 KB #experiments: 1988
71 Correct 59 ms 592 KB #experiments: 1888
72 Correct 64 ms 336 KB #experiments: 2110
73 Correct 64 ms 336 KB #experiments: 1936
74 Correct 77 ms 336 KB #experiments: 2058
75 Correct 75 ms 592 KB #experiments: 1880
76 Correct 74 ms 592 KB #experiments: 1958
77 Correct 67 ms 592 KB #experiments: 1926
78 Correct 77 ms 760 KB #experiments: 2032
79 Correct 61 ms 604 KB #experiments: 1839
80 Correct 68 ms 592 KB #experiments: 1952
81 Correct 77 ms 592 KB #experiments: 1976
82 Correct 123 ms 592 KB #experiments: 2409
83 Correct 272 ms 1104 KB #experiments: 1946
84 Correct 448 ms 1360 KB #experiments: 2425
85 Correct 56 ms 592 KB #experiments: 1129
86 Correct 177 ms 848 KB #experiments: 2494