답안 #56293 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56293	2018-07-11T02:37:06 Z	model_code	Genetics (BOI18_genetics)	C++17	100 / 100	737 ms	225784 KB

genetics

#include <iostream>
#include <cstdlib>
#include <cassert>
#include <string>
#include <vector>
using namespace std;

#define trav(a, x) for (auto& a : x)

int main() {
	cin.sync_with_stdio(false);
	int N, M, K;
	cin >> N >> M >> K;
	vector<string> input(N);
	for (int i = 0; i < N; ++i) cin >> input[i];
	bool expand = false;
	trav(x, input) trav(y, x) {
		if (y == 'G' || y == 'T') expand = true;
	}

	int realM = M;
	if (expand) {
		M *= 3;
		K *= 2;
	}
	int N2 = (N + 63) / 64;
	vector<vector<uint64_t>> strings(M, vector<uint64_t>(N2));
	vector<bool> iscandidate(N, true);
	vector<int> rc(N);
	vector<vector<int>> mat(N, vector<int>(M));
	int ncand = N;
	for (int i = 0; i < N; ++i) {
		string& str = input[i];
		int co = 0;
		for (int j = 0; j < realM; ++j) {
			int v = (str[j] >> 1) & 3;
			if (expand) {
				int v0 = 0, v1 = 0, v2 = 0;
				if (v == 0) v0 = v1 = v2 = 1;
				else if (v == 1) v0 = 1;
				else if (v == 2) v1 = 1;
				else if (v == 3) v2 = 1;
				int j0 = 3*j+0;
				int j1 = 3*j+1;
				int j2 = 3*j+2;

				strings[j0][i / 64] |= uint64_t(v0) << (i & 63);
				mat[i][j0] = 1 - 2 * v0;
				co += v0;
				strings[j1][i / 64] |= uint64_t(v1) << (i & 63);
				mat[i][j1] = 1 - 2 * v1;
				co += v1;
				strings[j2][i / 64] |= uint64_t(v2) << (i & 63);
				mat[i][j2] = 1 - 2 * v2;
				co += v2;
			} else {
				strings[j][i / 64] |= uint64_t(v) << (i & 63);
				mat[i][j] = 1 - 2 * v;
				co += v;
			}
		}
		rc[i] = co;
	}

	vector<bool> included(N);
	vector<uint64_t> bincluded(N2);
	vector<int> count(M, 0);
	while (ncand > 1) {
		unsigned int nincluded = 0;
		bincluded.assign(N2, 0);
		for (int i = 0; i < N; ++i) {
			included[i] = (rand() >> 14) & 1;
			bincluded[i / 64] |= uint64_t(included[i]) << (i & 63);
			nincluded += included[i] ? 1 : 0;
		}
		for (int j = 0; j < M; ++j) {
			int co = 0;
			for (int i = 0; i < N2; ++i)
				co += __builtin_popcountll(strings[j][i] & bincluded[i]);
			count[j] = co;
		}
		for (int i = 0; i < N; ++i) {
			if (!iscandidate[i]) continue;
			unsigned int sumdif = 0;
			for (int j = 0; j < M; ++j)
				sumdif += count[j] * mat[i][j];
			sumdif += nincluded * rc[i];
			unsigned int expectedsumdif = nincluded * K - (included[i] ? K : 0);
			if (sumdif != expectedsumdif) {
				iscandidate[i] = false;
				--ncand;
			}
		}
	}
	for (int i = 0; i < N; ++i) {
		if (iscandidate[i]) {
			cout << i + 1 << endl;
			return 0;
		}
	}
	cout << "nothing!" << endl;
	return 1;
}

Subtask #1
27.0 / 27.0

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

Subtask #2
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	14136 KB	Output is correct
2	Correct	46 ms	17340 KB	Output is correct
3	Correct	37 ms	16504 KB	Output is correct
4	Correct	12 ms	4092 KB	Output is correct
5	Correct	41 ms	17272 KB	Output is correct
6	Correct	41 ms	17272 KB	Output is correct
7	Correct	20 ms	7800 KB	Output is correct
8	Correct	27 ms	7676 KB	Output is correct
9	Correct	36 ms	15896 KB	Output is correct
10	Correct	47 ms	16120 KB	Output is correct
11	Correct	35 ms	14072 KB	Output is correct
12	Correct	40 ms	14156 KB	Output is correct
13	Correct	34 ms	14072 KB	Output is correct
14	Correct	37 ms	12140 KB	Output is correct
15	Correct	31 ms	12280 KB	Output is correct
16	Correct	32 ms	12152 KB	Output is correct
17	Correct	36 ms	16504 KB	Output is correct
18	Correct	37 ms	16376 KB	Output is correct
19	Correct	41 ms	16632 KB	Output is correct
20	Correct	42 ms	16376 KB	Output is correct
21	Correct	38 ms	16504 KB	Output is correct
22	Correct	38 ms	16380 KB	Output is correct
23	Correct	44 ms	16504 KB	Output is correct
24	Correct	35 ms	16504 KB	Output is correct
25	Correct	41 ms	16632 KB	Output is correct
26	Correct	38 ms	16504 KB	Output is correct
27	Correct	39 ms	16376 KB	Output is correct
28	Correct	40 ms	16376 KB	Output is correct
29	Correct	38 ms	16632 KB	Output is correct
30	Correct	37 ms	17272 KB	Output is correct
31	Correct	39 ms	17272 KB	Output is correct
32	Correct	36 ms	17272 KB	Output is correct
33	Correct	5 ms	376 KB	Output is correct
34	Correct	5 ms	376 KB	Output is correct
35	Correct	5 ms	444 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	14136 KB	Output is correct
2	Correct	46 ms	17340 KB	Output is correct
3	Correct	37 ms	16504 KB	Output is correct
4	Correct	12 ms	4092 KB	Output is correct
5	Correct	41 ms	17272 KB	Output is correct
6	Correct	41 ms	17272 KB	Output is correct
7	Correct	20 ms	7800 KB	Output is correct
8	Correct	27 ms	7676 KB	Output is correct
9	Correct	36 ms	15896 KB	Output is correct
10	Correct	47 ms	16120 KB	Output is correct
11	Correct	35 ms	14072 KB	Output is correct
12	Correct	40 ms	14156 KB	Output is correct
13	Correct	34 ms	14072 KB	Output is correct
14	Correct	37 ms	12140 KB	Output is correct
15	Correct	31 ms	12280 KB	Output is correct
16	Correct	32 ms	12152 KB	Output is correct
17	Correct	36 ms	16504 KB	Output is correct
18	Correct	37 ms	16376 KB	Output is correct
19	Correct	41 ms	16632 KB	Output is correct
20	Correct	42 ms	16376 KB	Output is correct
21	Correct	38 ms	16504 KB	Output is correct
22	Correct	38 ms	16380 KB	Output is correct
23	Correct	44 ms	16504 KB	Output is correct
24	Correct	35 ms	16504 KB	Output is correct
25	Correct	41 ms	16632 KB	Output is correct
26	Correct	38 ms	16504 KB	Output is correct
27	Correct	39 ms	16376 KB	Output is correct
28	Correct	40 ms	16376 KB	Output is correct
29	Correct	38 ms	16632 KB	Output is correct
30	Correct	37 ms	17272 KB	Output is correct
31	Correct	39 ms	17272 KB	Output is correct
32	Correct	36 ms	17272 KB	Output is correct
33	Correct	5 ms	376 KB	Output is correct
34	Correct	5 ms	376 KB	Output is correct
35	Correct	5 ms	444 KB	Output is correct
36	Correct	174 ms	77268 KB	Output is correct
37	Correct	189 ms	87672 KB	Output is correct
38	Correct	187 ms	86008 KB	Output is correct
39	Correct	72 ms	31352 KB	Output is correct
40	Correct	190 ms	87672 KB	Output is correct
41	Correct	105 ms	44152 KB	Output is correct
42	Correct	96 ms	44180 KB	Output is correct
43	Correct	128 ms	62336 KB	Output is correct
44	Correct	177 ms	87928 KB	Output is correct
45	Correct	183 ms	87928 KB	Output is correct
46	Correct	190 ms	88060 KB	Output is correct
47	Correct	155 ms	77308 KB	Output is correct
48	Correct	153 ms	77304 KB	Output is correct
49	Correct	135 ms	66188 KB	Output is correct
50	Correct	136 ms	66040 KB	Output is correct
51	Correct	140 ms	73976 KB	Output is correct
52	Correct	232 ms	85752 KB	Output is correct
53	Correct	193 ms	85880 KB	Output is correct
54	Correct	191 ms	83196 KB	Output is correct
55	Correct	167 ms	83192 KB	Output is correct
56	Correct	181 ms	83352 KB	Output is correct
57	Correct	204 ms	86008 KB	Output is correct
58	Correct	191 ms	86008 KB	Output is correct
59	Correct	177 ms	85624 KB	Output is correct
60	Correct	185 ms	86136 KB	Output is correct
61	Correct	202 ms	85624 KB	Output is correct
62	Correct	183 ms	85356 KB	Output is correct
63	Correct	191 ms	86136 KB	Output is correct
64	Correct	200 ms	86008 KB	Output is correct
65	Correct	228 ms	85752 KB	Output is correct
66	Correct	181 ms	85984 KB	Output is correct
67	Correct	174 ms	86136 KB	Output is correct
68	Correct	188 ms	86136 KB	Output is correct
69	Correct	187 ms	85752 KB	Output is correct
70	Correct	187 ms	86008 KB	Output is correct
71	Correct	240 ms	85624 KB	Output is correct
72	Correct	226 ms	86268 KB	Output is correct
73	Correct	177 ms	85880 KB	Output is correct
74	Correct	5 ms	376 KB	Output is correct
75	Correct	5 ms	376 KB	Output is correct
76	Correct	5 ms	376 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	504 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	6 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	504 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	6 ms	504 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	6 ms	504 KB	Output is correct
15	Correct	6 ms	504 KB	Output is correct
16	Correct	6 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	39 ms	14136 KB	Output is correct
19	Correct	46 ms	17340 KB	Output is correct
20	Correct	37 ms	16504 KB	Output is correct
21	Correct	12 ms	4092 KB	Output is correct
22	Correct	41 ms	17272 KB	Output is correct
23	Correct	41 ms	17272 KB	Output is correct
24	Correct	20 ms	7800 KB	Output is correct
25	Correct	27 ms	7676 KB	Output is correct
26	Correct	36 ms	15896 KB	Output is correct
27	Correct	47 ms	16120 KB	Output is correct
28	Correct	35 ms	14072 KB	Output is correct
29	Correct	40 ms	14156 KB	Output is correct
30	Correct	34 ms	14072 KB	Output is correct
31	Correct	37 ms	12140 KB	Output is correct
32	Correct	31 ms	12280 KB	Output is correct
33	Correct	32 ms	12152 KB	Output is correct
34	Correct	36 ms	16504 KB	Output is correct
35	Correct	37 ms	16376 KB	Output is correct
36	Correct	41 ms	16632 KB	Output is correct
37	Correct	42 ms	16376 KB	Output is correct
38	Correct	38 ms	16504 KB	Output is correct
39	Correct	38 ms	16380 KB	Output is correct
40	Correct	44 ms	16504 KB	Output is correct
41	Correct	35 ms	16504 KB	Output is correct
42	Correct	41 ms	16632 KB	Output is correct
43	Correct	38 ms	16504 KB	Output is correct
44	Correct	39 ms	16376 KB	Output is correct
45	Correct	40 ms	16376 KB	Output is correct
46	Correct	38 ms	16632 KB	Output is correct
47	Correct	37 ms	17272 KB	Output is correct
48	Correct	39 ms	17272 KB	Output is correct
49	Correct	36 ms	17272 KB	Output is correct
50	Correct	5 ms	376 KB	Output is correct
51	Correct	5 ms	376 KB	Output is correct
52	Correct	5 ms	444 KB	Output is correct
53	Correct	174 ms	77268 KB	Output is correct
54	Correct	189 ms	87672 KB	Output is correct
55	Correct	187 ms	86008 KB	Output is correct
56	Correct	72 ms	31352 KB	Output is correct
57	Correct	190 ms	87672 KB	Output is correct
58	Correct	105 ms	44152 KB	Output is correct
59	Correct	96 ms	44180 KB	Output is correct
60	Correct	128 ms	62336 KB	Output is correct
61	Correct	177 ms	87928 KB	Output is correct
62	Correct	183 ms	87928 KB	Output is correct
63	Correct	190 ms	88060 KB	Output is correct
64	Correct	155 ms	77308 KB	Output is correct
65	Correct	153 ms	77304 KB	Output is correct
66	Correct	135 ms	66188 KB	Output is correct
67	Correct	136 ms	66040 KB	Output is correct
68	Correct	140 ms	73976 KB	Output is correct
69	Correct	232 ms	85752 KB	Output is correct
70	Correct	193 ms	85880 KB	Output is correct
71	Correct	191 ms	83196 KB	Output is correct
72	Correct	167 ms	83192 KB	Output is correct
73	Correct	181 ms	83352 KB	Output is correct
74	Correct	204 ms	86008 KB	Output is correct
75	Correct	191 ms	86008 KB	Output is correct
76	Correct	177 ms	85624 KB	Output is correct
77	Correct	185 ms	86136 KB	Output is correct
78	Correct	202 ms	85624 KB	Output is correct
79	Correct	183 ms	85356 KB	Output is correct
80	Correct	191 ms	86136 KB	Output is correct
81	Correct	200 ms	86008 KB	Output is correct
82	Correct	228 ms	85752 KB	Output is correct
83	Correct	181 ms	85984 KB	Output is correct
84	Correct	174 ms	86136 KB	Output is correct
85	Correct	188 ms	86136 KB	Output is correct
86	Correct	187 ms	85752 KB	Output is correct
87	Correct	187 ms	86008 KB	Output is correct
88	Correct	240 ms	85624 KB	Output is correct
89	Correct	226 ms	86268 KB	Output is correct
90	Correct	177 ms	85880 KB	Output is correct
91	Correct	5 ms	376 KB	Output is correct
92	Correct	5 ms	376 KB	Output is correct
93	Correct	5 ms	376 KB	Output is correct
94	Correct	599 ms	212216 KB	Output is correct
95	Correct	549 ms	225528 KB	Output is correct
96	Correct	737 ms	221888 KB	Output is correct
97	Correct	315 ms	121720 KB	Output is correct
98	Correct	223 ms	81016 KB	Output is correct
99	Correct	213 ms	89336 KB	Output is correct
100	Correct	325 ms	114168 KB	Output is correct
101	Correct	333 ms	114040 KB	Output is correct
102	Correct	422 ms	160740 KB	Output is correct
103	Correct	185 ms	89848 KB	Output is correct
104	Correct	647 ms	225568 KB	Output is correct
105	Correct	640 ms	225708 KB	Output is correct
106	Correct	579 ms	214520 KB	Output is correct
107	Correct	176 ms	78968 KB	Output is correct
108	Correct	140 ms	68088 KB	Output is correct
109	Correct	569 ms	195224 KB	Output is correct
110	Correct	498 ms	185976 KB	Output is correct
111	Correct	627 ms	225784 KB	Output is correct
112	Correct	615 ms	222840 KB	Output is correct
113	Correct	523 ms	214648 KB	Output is correct
114	Correct	178 ms	84984 KB	Output is correct
115	Correct	580 ms	214648 KB	Output is correct
116	Correct	630 ms	222712 KB	Output is correct
117	Correct	614 ms	223992 KB	Output is correct
118	Correct	580 ms	223612 KB	Output is correct
119	Correct	684 ms	222752 KB	Output is correct
120	Correct	580 ms	223784 KB	Output is correct
121	Correct	163 ms	79608 KB	Output is correct
122	Correct	192 ms	89592 KB	Output is correct
123	Correct	194 ms	88440 KB	Output is correct
124	Correct	5 ms	376 KB	Output is correct
125	Correct	5 ms	376 KB	Output is correct
126	Correct	5 ms	376 KB	Output is correct

답안 #56293

Compilation message

Subtask #1 27.0 / 27.0

Subtask #2 19.0 / 19.0

Subtask #3 28.0 / 28.0

Subtask #4 26.0 / 26.0

Subtask #1
27.0 / 27.0

Subtask #2
19.0 / 19.0

Subtask #3
28.0 / 28.0

Subtask #4
26.0 / 26.0