oj.uz

Submission #674345

# Submission time Handle Problem Language Result Execution time Memory
674345 2022-12-23T18:13:02 Z rainboy Minerals (JOI19_minerals) C++17
100 / 100
 71 ms 8260 KB 
/* https://www.ioi-jp.org/camp/2019/2019-sp-tasks/day4/minerals-review.pdf */
#include "minerals.h"
#include <cstring>
 
const int N = 43000, L = 19;
 
int k;
 
int Query_(int i) {
	int k_ = Query(i + 1);
	if (k_ == k)
		return 0;
	k = k_;
	return 1;
}
 
int tt[N * 2], ii[2][N], ii_[1 << L], nn[2], aa[N], bb[N];
int aaa[L * 2 + 2][1 << L], nn_[L * 2 + 2], kk[1 << L];
 
void Solve(int n) {
	for (int i = 0; i < n * 2; i++) {
		tt[i] = !Query_(i);
		ii[tt[i]][nn[tt[i]]++] = i;
	}
	for (int a = 0; a < 1 << L; a++) {
		int k = 0, l_ = -1;
		for (int l = 0; l < L; l++)
			if ((a >> l & 1) != (l == 0 ? 0 : (a >> l - 1 & 1)))
				k++, l_ = l;
		int w = a == 0 ? 0 : k + l_ + 2;
		aaa[w][nn_[w]++] = a;
	}
	for (int i = 0, w = 0; i < n; i++) {
		while (nn_[w] == 0)
			w++;
		aa[i] = aaa[w][--nn_[w]];
	}
	for (int l = 0; l < L; l++) {
		for (int i = 0; i < n; i++)
			if ((aa[i] >> l & 1) != (l == 0 ? 0 : (aa[i] >> l - 1 & 1)))
				Query_(ii[0][i]);
		memset(kk, 0, (1 << L) * sizeof *kk);
		for (int i = 0; i < n; i++)
			kk[aa[i] & (1 << l + 1) - 1]++;
		for (int i = 0; i < n; i++) {
			if (kk[bb[i]] == 0 || kk[bb[i] | 1 << l] != 0 && Query_(ii[1][i]))
				bb[i] |= 1 << l;
			kk[bb[i]]--;
		}
	}
	for (int i = 0; i < n; i++)
		ii_[aa[i]] = ii[0][i];
	for (int i = 0; i < n; i++)
		Answer(ii_[bb[i]] + 1, ii[1][i] + 1);
}

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:28:46: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   28 |    if ((a >> l & 1) != (l == 0 ? 0 : (a >> l - 1 & 1)))
      |                                            ~~^~~
minerals.cpp:40:54: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   40 |    if ((aa[i] >> l & 1) != (l == 0 ? 0 : (aa[i] >> l - 1 & 1)))
      |                                                    ~~^~~
minerals.cpp:44:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   44 |    kk[aa[i] & (1 << l + 1) - 1]++;
      |                     ~~^~~
minerals.cpp:44:28: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   44 |    kk[aa[i] & (1 << l + 1) - 1]++;
      |               ~~~~~~~~~~~~~^~~
minerals.cpp:46:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   46 |    if (kk[bb[i]] == 0 || kk[bb[i] | 1 << l] != 0 && Query_(ii[1][i]))
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4668 KB Output is correct
2 Correct 36 ms 4672 KB Output is correct
3 Correct 36 ms 4616 KB Output is correct
4 Correct 38 ms 4656 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4716 KB Output is correct
2 Correct 37 ms 4716 KB Output is correct
3 Correct 38 ms 4984 KB Output is correct
4 Correct 44 ms 5192 KB Output is correct
5 Correct 47 ms 5900 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4668 KB Output is correct
2 Correct 36 ms 4672 KB Output is correct
3 Correct 36 ms 4616 KB Output is correct
4 Correct 38 ms 4656 KB Output is correct
5 Correct 36 ms 4716 KB Output is correct
6 Correct 37 ms 4716 KB Output is correct
7 Correct 38 ms 4984 KB Output is correct
8 Correct 44 ms 5192 KB Output is correct
9 Correct 47 ms 5900 KB Output is correct
10 Correct 39 ms 4676 KB Output is correct
11 Correct 43 ms 5632 KB Output is correct
12 Correct 46 ms 6000 KB Output is correct
13 Correct 44 ms 5976 KB Output is correct
14 Correct 44 ms 5960 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4668 KB Output is correct
2 Correct 36 ms 4672 KB Output is correct
3 Correct 36 ms 4616 KB Output is correct
4 Correct 38 ms 4656 KB Output is correct
5 Correct 36 ms 4716 KB Output is correct
6 Correct 37 ms 4716 KB Output is correct
7 Correct 38 ms 4984 KB Output is correct
8 Correct 44 ms 5192 KB Output is correct
9 Correct 47 ms 5900 KB Output is correct
10 Correct 39 ms 4676 KB Output is correct
11 Correct 43 ms 5632 KB Output is correct
12 Correct 46 ms 6000 KB Output is correct
13 Correct 44 ms 5976 KB Output is correct
14 Correct 44 ms 5960 KB Output is correct
15 Correct 67 ms 7872 KB Output is correct
16 Correct 62 ms 7868 KB Output is correct
17 Correct 57 ms 7820 KB Output is correct
18 Correct 57 ms 7700 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4668 KB Output is correct
2 Correct 36 ms 4672 KB Output is correct
3 Correct 36 ms 4616 KB Output is correct
4 Correct 38 ms 4656 KB Output is correct
5 Correct 36 ms 4716 KB Output is correct
6 Correct 37 ms 4716 KB Output is correct
7 Correct 38 ms 4984 KB Output is correct
8 Correct 44 ms 5192 KB Output is correct
9 Correct 47 ms 5900 KB Output is correct
10 Correct 39 ms 4676 KB Output is correct
11 Correct 43 ms 5632 KB Output is correct
12 Correct 46 ms 6000 KB Output is correct
13 Correct 44 ms 5976 KB Output is correct
14 Correct 44 ms 5960 KB Output is correct
15 Correct 67 ms 7872 KB Output is correct
16 Correct 62 ms 7868 KB Output is correct
17 Correct 57 ms 7820 KB Output is correct
18 Correct 57 ms 7700 KB Output is correct
19 Correct 71 ms 7980 KB Output is correct
20 Correct 64 ms 8048 KB Output is correct
21 Correct 56 ms 7952 KB Output is correct
22 Correct 62 ms 7832 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4668 KB Output is correct
2 Correct 36 ms 4672 KB Output is correct
3 Correct 36 ms 4616 KB Output is correct
4 Correct 38 ms 4656 KB Output is correct
5 Correct 36 ms 4716 KB Output is correct
6 Correct 37 ms 4716 KB Output is correct
7 Correct 38 ms 4984 KB Output is correct
8 Correct 44 ms 5192 KB Output is correct
9 Correct 47 ms 5900 KB Output is correct
10 Correct 39 ms 4676 KB Output is correct
11 Correct 43 ms 5632 KB Output is correct
12 Correct 46 ms 6000 KB Output is correct
13 Correct 44 ms 5976 KB Output is correct
14 Correct 44 ms 5960 KB Output is correct
15 Correct 67 ms 7872 KB Output is correct
16 Correct 62 ms 7868 KB Output is correct
17 Correct 57 ms 7820 KB Output is correct
18 Correct 57 ms 7700 KB Output is correct
19 Correct 71 ms 7980 KB Output is correct
20 Correct 64 ms 8048 KB Output is correct
21 Correct 56 ms 7952 KB Output is correct
22 Correct 62 ms 7832 KB Output is correct
23 Correct 67 ms 8132 KB Output is correct
24 Correct 69 ms 8072 KB Output is correct
25 Correct 57 ms 8064 KB Output is correct
26 Correct 61 ms 7888 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4668 KB Output is correct
2 Correct 36 ms 4672 KB Output is correct
3 Correct 36 ms 4616 KB Output is correct
4 Correct 38 ms 4656 KB Output is correct
5 Correct 36 ms 4716 KB Output is correct
6 Correct 37 ms 4716 KB Output is correct
7 Correct 38 ms 4984 KB Output is correct
8 Correct 44 ms 5192 KB Output is correct
9 Correct 47 ms 5900 KB Output is correct
10 Correct 39 ms 4676 KB Output is correct
11 Correct 43 ms 5632 KB Output is correct
12 Correct 46 ms 6000 KB Output is correct
13 Correct 44 ms 5976 KB Output is correct
14 Correct 44 ms 5960 KB Output is correct
15 Correct 67 ms 7872 KB Output is correct
16 Correct 62 ms 7868 KB Output is correct
17 Correct 57 ms 7820 KB Output is correct
18 Correct 57 ms 7700 KB Output is correct
19 Correct 71 ms 7980 KB Output is correct
20 Correct 64 ms 8048 KB Output is correct
21 Correct 56 ms 7952 KB Output is correct
22 Correct 62 ms 7832 KB Output is correct
23 Correct 67 ms 8132 KB Output is correct
24 Correct 69 ms 8072 KB Output is correct
25 Correct 57 ms 8064 KB Output is correct
26 Correct 61 ms 7888 KB Output is correct
27 Correct 64 ms 8044 KB Output is correct
28 Correct 70 ms 8136 KB Output is correct
29 Correct 65 ms 8048 KB Output is correct
30 Correct 64 ms 8008 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4668 KB Output is correct
2 Correct 36 ms 4672 KB Output is correct
3 Correct 36 ms 4616 KB Output is correct
4 Correct 38 ms 4656 KB Output is correct
5 Correct 36 ms 4716 KB Output is correct
6 Correct 37 ms 4716 KB Output is correct
7 Correct 38 ms 4984 KB Output is correct
8 Correct 44 ms 5192 KB Output is correct
9 Correct 47 ms 5900 KB Output is correct
10 Correct 39 ms 4676 KB Output is correct
11 Correct 43 ms 5632 KB Output is correct
12 Correct 46 ms 6000 KB Output is correct
13 Correct 44 ms 5976 KB Output is correct
14 Correct 44 ms 5960 KB Output is correct
15 Correct 67 ms 7872 KB Output is correct
16 Correct 62 ms 7868 KB Output is correct
17 Correct 57 ms 7820 KB Output is correct
18 Correct 57 ms 7700 KB Output is correct
19 Correct 71 ms 7980 KB Output is correct
20 Correct 64 ms 8048 KB Output is correct
21 Correct 56 ms 7952 KB Output is correct
22 Correct 62 ms 7832 KB Output is correct
23 Correct 67 ms 8132 KB Output is correct
24 Correct 69 ms 8072 KB Output is correct
25 Correct 57 ms 8064 KB Output is correct
26 Correct 61 ms 7888 KB Output is correct
27 Correct 64 ms 8044 KB Output is correct
28 Correct 70 ms 8136 KB Output is correct
29 Correct 65 ms 8048 KB Output is correct
30 Correct 64 ms 8008 KB Output is correct
31 Correct 64 ms 8196 KB Output is correct
32 Correct 65 ms 8184 KB Output is correct
33 Correct 58 ms 8204 KB Output is correct
34 Correct 59 ms 7964 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4668 KB Output is correct
2 Correct 36 ms 4672 KB Output is correct
3 Correct 36 ms 4616 KB Output is correct
4 Correct 38 ms 4656 KB Output is correct
5 Correct 36 ms 4716 KB Output is correct
6 Correct 37 ms 4716 KB Output is correct
7 Correct 38 ms 4984 KB Output is correct
8 Correct 44 ms 5192 KB Output is correct
9 Correct 47 ms 5900 KB Output is correct
10 Correct 39 ms 4676 KB Output is correct
11 Correct 43 ms 5632 KB Output is correct
12 Correct 46 ms 6000 KB Output is correct
13 Correct 44 ms 5976 KB Output is correct
14 Correct 44 ms 5960 KB Output is correct
15 Correct 67 ms 7872 KB Output is correct
16 Correct 62 ms 7868 KB Output is correct
17 Correct 57 ms 7820 KB Output is correct
18 Correct 57 ms 7700 KB Output is correct
19 Correct 71 ms 7980 KB Output is correct
20 Correct 64 ms 8048 KB Output is correct
21 Correct 56 ms 7952 KB Output is correct
22 Correct 62 ms 7832 KB Output is correct
23 Correct 67 ms 8132 KB Output is correct
24 Correct 69 ms 8072 KB Output is correct
25 Correct 57 ms 8064 KB Output is correct
26 Correct 61 ms 7888 KB Output is correct
27 Correct 64 ms 8044 KB Output is correct
28 Correct 70 ms 8136 KB Output is correct
29 Correct 65 ms 8048 KB Output is correct
30 Correct 64 ms 8008 KB Output is correct
31 Correct 64 ms 8196 KB Output is correct
32 Correct 65 ms 8184 KB Output is correct
33 Correct 58 ms 8204 KB Output is correct
34 Correct 59 ms 7964 KB Output is correct
35 Correct 69 ms 8148 KB Output is correct
36 Correct 66 ms 8188 KB Output is correct
37 Correct 63 ms 8260 KB Output is correct
38 Correct 62 ms 8036 KB Output is correct