oj.uz

답안 #395194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395194 2021-04-28T01:31:11 Z wenqi Genetics (BOI18_genetics) C++14
100 / 100
 539 ms 33620 KB 
#include <bits/stdc++.h>

using namespace std;

int N, M, K;

using H = uint64_t;

#define P1 30881

const H P2 = (1ll << 45) - 1;

char dna[4169][4169];

H coef[4169];

int idx[256];

uint64_t Y[6];
uint64_t E[4169];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> K;

	coef[0] = 1;
	for(int i = 1; i <= N; i++) {
		cin >> dna[i];
		coef[i] = (coef[i - 1] * P1) & P2;
	}

	idx['A'] = 0;
	idx['C'] = 1;
	idx['G'] = 2;
	idx['T'] = 3;

	for(int i = 0; i < M; i++) {
		Y[0] = 0; Y[1] = 0; Y[2] = 0; Y[3] = 0;
		for(int j = 1; j <= N; j++) {
			int w = idx[dna[j][i]];
			Y[w] += coef[j];
			Y[w] &= P2;
		}

		for(int j = 1; j <= N; j++) {
			for(int ii = 0; ii < 4; ii++) {
				if(idx[dna[j][i]] != ii) {
					E[j] += Y[ii];
					E[j] &= P2;
				}
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		H needed = 0;

		for(int j = 1; j <= N; j++) {
			if(i == j) continue;
			needed = (needed + coef[j] * K) & P2;
		}

		H T = E[i];

		if(T == needed) {
			cout << i << '\n';
			return 0;
		}
	}
	return 0;
}

Compilation message

genetics.cpp: In function 'int main()':
genetics.cpp:42:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |    int w = idx[dna[j][i]];
      |                ~~~~~~~~^
genetics.cpp:49:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |     if(idx[dna[j][i]] != ii) {
      |            ~~~~~~~~^

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 332 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 6604 KB Output is correct
2 Correct 83 ms 10828 KB Output is correct
3 Correct 87 ms 10340 KB Output is correct
4 Correct 16 ms 5580 KB Output is correct
5 Correct 91 ms 10864 KB Output is correct
6 Correct 83 ms 10856 KB Output is correct
7 Correct 27 ms 4812 KB Output is correct
8 Correct 22 ms 4812 KB Output is correct
9 Correct 81 ms 10324 KB Output is correct
10 Correct 78 ms 10316 KB Output is correct
11 Correct 61 ms 9032 KB Output is correct
12 Correct 62 ms 9132 KB Output is correct
13 Correct 65 ms 9036 KB Output is correct
14 Correct 46 ms 7816 KB Output is correct
15 Correct 46 ms 7884 KB Output is correct
16 Correct 51 ms 8524 KB Output is correct
17 Correct 75 ms 10404 KB Output is correct
18 Correct 76 ms 10232 KB Output is correct
19 Correct 80 ms 10436 KB Output is correct
20 Correct 60 ms 10308 KB Output is correct
21 Correct 70 ms 10396 KB Output is correct
22 Correct 75 ms 10316 KB Output is correct
23 Correct 74 ms 10316 KB Output is correct
24 Correct 70 ms 10316 KB Output is correct
25 Correct 68 ms 10280 KB Output is correct
26 Correct 73 ms 10364 KB Output is correct
27 Correct 67 ms 10316 KB Output is correct
28 Correct 67 ms 10292 KB Output is correct
29 Correct 77 ms 10260 KB Output is correct
30 Correct 57 ms 10948 KB Output is correct
31 Correct 60 ms 10864 KB Output is correct
32 Correct 79 ms 10968 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 712 KB Output is correct
35 Correct 1 ms 332 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 6604 KB Output is correct
2 Correct 83 ms 10828 KB Output is correct
3 Correct 87 ms 10340 KB Output is correct
4 Correct 16 ms 5580 KB Output is correct
5 Correct 91 ms 10864 KB Output is correct
6 Correct 83 ms 10856 KB Output is correct
7 Correct 27 ms 4812 KB Output is correct
8 Correct 22 ms 4812 KB Output is correct
9 Correct 81 ms 10324 KB Output is correct
10 Correct 78 ms 10316 KB Output is correct
11 Correct 61 ms 9032 KB Output is correct
12 Correct 62 ms 9132 KB Output is correct
13 Correct 65 ms 9036 KB Output is correct
14 Correct 46 ms 7816 KB Output is correct
15 Correct 46 ms 7884 KB Output is correct
16 Correct 51 ms 8524 KB Output is correct
17 Correct 75 ms 10404 KB Output is correct
18 Correct 76 ms 10232 KB Output is correct
19 Correct 80 ms 10436 KB Output is correct
20 Correct 60 ms 10308 KB Output is correct
21 Correct 70 ms 10396 KB Output is correct
22 Correct 75 ms 10316 KB Output is correct
23 Correct 74 ms 10316 KB Output is correct
24 Correct 70 ms 10316 KB Output is correct
25 Correct 68 ms 10280 KB Output is correct
26 Correct 73 ms 10364 KB Output is correct
27 Correct 67 ms 10316 KB Output is correct
28 Correct 67 ms 10292 KB Output is correct
29 Correct 77 ms 10260 KB Output is correct
30 Correct 57 ms 10948 KB Output is correct
31 Correct 60 ms 10864 KB Output is correct
32 Correct 79 ms 10968 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 712 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 323 ms 29264 KB Output is correct
37 Correct 311 ms 33604 KB Output is correct
38 Correct 383 ms 32708 KB Output is correct
39 Correct 154 ms 20348 KB Output is correct
40 Correct 486 ms 33620 KB Output is correct
41 Correct 224 ms 16836 KB Output is correct
42 Correct 211 ms 16876 KB Output is correct
43 Correct 353 ms 26152 KB Output is correct
44 Correct 485 ms 33476 KB Output is correct
45 Correct 472 ms 33552 KB Output is correct
46 Correct 494 ms 33604 KB Output is correct
47 Correct 436 ms 29256 KB Output is correct
48 Correct 424 ms 29380 KB Output is correct
49 Correct 395 ms 25156 KB Output is correct
50 Correct 380 ms 25260 KB Output is correct
51 Correct 385 ms 28332 KB Output is correct
52 Correct 464 ms 32768 KB Output is correct
53 Correct 523 ms 32652 KB Output is correct
54 Correct 414 ms 32336 KB Output is correct
55 Correct 453 ms 32332 KB Output is correct
56 Correct 464 ms 32340 KB Output is correct
57 Correct 498 ms 32768 KB Output is correct
58 Correct 487 ms 32768 KB Output is correct
59 Correct 481 ms 32588 KB Output is correct
60 Correct 471 ms 32840 KB Output is correct
61 Correct 472 ms 32704 KB Output is correct
62 Correct 466 ms 32472 KB Output is correct
63 Correct 454 ms 32820 KB Output is correct
64 Correct 437 ms 32708 KB Output is correct
65 Correct 446 ms 32624 KB Output is correct
66 Correct 427 ms 32704 KB Output is correct
67 Correct 418 ms 32776 KB Output is correct
68 Correct 473 ms 32716 KB Output is correct
69 Correct 472 ms 32692 KB Output is correct
70 Correct 472 ms 32836 KB Output is correct
71 Correct 459 ms 32616 KB Output is correct
72 Correct 463 ms 32848 KB Output is correct
73 Correct 464 ms 32628 KB Output is correct
74 Correct 1 ms 332 KB Output is correct
75 Correct 1 ms 716 KB Output is correct
76 Correct 1 ms 304 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 71 ms 6604 KB Output is correct
19 Correct 83 ms 10828 KB Output is correct
20 Correct 87 ms 10340 KB Output is correct
21 Correct 16 ms 5580 KB Output is correct
22 Correct 91 ms 10864 KB Output is correct
23 Correct 83 ms 10856 KB Output is correct
24 Correct 27 ms 4812 KB Output is correct
25 Correct 22 ms 4812 KB Output is correct
26 Correct 81 ms 10324 KB Output is correct
27 Correct 78 ms 10316 KB Output is correct
28 Correct 61 ms 9032 KB Output is correct
29 Correct 62 ms 9132 KB Output is correct
30 Correct 65 ms 9036 KB Output is correct
31 Correct 46 ms 7816 KB Output is correct
32 Correct 46 ms 7884 KB Output is correct
33 Correct 51 ms 8524 KB Output is correct
34 Correct 75 ms 10404 KB Output is correct
35 Correct 76 ms 10232 KB Output is correct
36 Correct 80 ms 10436 KB Output is correct
37 Correct 60 ms 10308 KB Output is correct
38 Correct 70 ms 10396 KB Output is correct
39 Correct 75 ms 10316 KB Output is correct
40 Correct 74 ms 10316 KB Output is correct
41 Correct 70 ms 10316 KB Output is correct
42 Correct 68 ms 10280 KB Output is correct
43 Correct 73 ms 10364 KB Output is correct
44 Correct 67 ms 10316 KB Output is correct
45 Correct 67 ms 10292 KB Output is correct
46 Correct 77 ms 10260 KB Output is correct
47 Correct 57 ms 10948 KB Output is correct
48 Correct 60 ms 10864 KB Output is correct
49 Correct 79 ms 10968 KB Output is correct
50 Correct 1 ms 332 KB Output is correct
51 Correct 1 ms 712 KB Output is correct
52 Correct 1 ms 332 KB Output is correct
53 Correct 323 ms 29264 KB Output is correct
54 Correct 311 ms 33604 KB Output is correct
55 Correct 383 ms 32708 KB Output is correct
56 Correct 154 ms 20348 KB Output is correct
57 Correct 486 ms 33620 KB Output is correct
58 Correct 224 ms 16836 KB Output is correct
59 Correct 211 ms 16876 KB Output is correct
60 Correct 353 ms 26152 KB Output is correct
61 Correct 485 ms 33476 KB Output is correct
62 Correct 472 ms 33552 KB Output is correct
63 Correct 494 ms 33604 KB Output is correct
64 Correct 436 ms 29256 KB Output is correct
65 Correct 424 ms 29380 KB Output is correct
66 Correct 395 ms 25156 KB Output is correct
67 Correct 380 ms 25260 KB Output is correct
68 Correct 385 ms 28332 KB Output is correct
69 Correct 464 ms 32768 KB Output is correct
70 Correct 523 ms 32652 KB Output is correct
71 Correct 414 ms 32336 KB Output is correct
72 Correct 453 ms 32332 KB Output is correct
73 Correct 464 ms 32340 KB Output is correct
74 Correct 498 ms 32768 KB Output is correct
75 Correct 487 ms 32768 KB Output is correct
76 Correct 481 ms 32588 KB Output is correct
77 Correct 471 ms 32840 KB Output is correct
78 Correct 472 ms 32704 KB Output is correct
79 Correct 466 ms 32472 KB Output is correct
80 Correct 454 ms 32820 KB Output is correct
81 Correct 437 ms 32708 KB Output is correct
82 Correct 446 ms 32624 KB Output is correct
83 Correct 427 ms 32704 KB Output is correct
84 Correct 418 ms 32776 KB Output is correct
85 Correct 473 ms 32716 KB Output is correct
86 Correct 472 ms 32692 KB Output is correct
87 Correct 472 ms 32836 KB Output is correct
88 Correct 459 ms 32616 KB Output is correct
89 Correct 463 ms 32848 KB Output is correct
90 Correct 464 ms 32628 KB Output is correct
91 Correct 1 ms 332 KB Output is correct
92 Correct 1 ms 716 KB Output is correct
93 Correct 1 ms 304 KB Output is correct
94 Correct 487 ms 31720 KB Output is correct
95 Correct 435 ms 33548 KB Output is correct
96 Correct 530 ms 32920 KB Output is correct
97 Correct 238 ms 18048 KB Output is correct
98 Correct 180 ms 20312 KB Output is correct
99 Correct 467 ms 33480 KB Output is correct
100 Correct 212 ms 16916 KB Output is correct
101 Correct 212 ms 16924 KB Output is correct
102 Correct 350 ms 26144 KB Output is correct
103 Correct 486 ms 33476 KB Output is correct
104 Correct 539 ms 33472 KB Output is correct
105 Correct 523 ms 33568 KB Output is correct
106 Correct 517 ms 31812 KB Output is correct
107 Correct 433 ms 29344 KB Output is correct
108 Correct 360 ms 25316 KB Output is correct
109 Correct 461 ms 28924 KB Output is correct
110 Correct 405 ms 28112 KB Output is correct
111 Correct 507 ms 33400 KB Output is correct
112 Correct 539 ms 33060 KB Output is correct
113 Correct 439 ms 32328 KB Output is correct
114 Correct 418 ms 32220 KB Output is correct
115 Correct 455 ms 32332 KB Output is correct
116 Correct 534 ms 33020 KB Output is correct
117 Correct 531 ms 33224 KB Output is correct
118 Correct 532 ms 33120 KB Output is correct
119 Correct 531 ms 33016 KB Output is correct
120 Correct 525 ms 33160 KB Output is correct
121 Correct 433 ms 29356 KB Output is correct
122 Correct 443 ms 33512 KB Output is correct
123 Correct 489 ms 32696 KB Output is correct
124 Correct 1 ms 332 KB Output is correct
125 Correct 1 ms 716 KB Output is correct
126 Correct 1 ms 332 KB Output is correct