// I am now here, but I have yet to prove that I am worthy of my place here.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using ll = long long;
const ll maxN = 4101;
const ll mod = 1'690'758'499;
const ll maxW = 1'000'000;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll getRand(ll l, ll r) {
return uniform_int_distribution<ll>(l, r)(rng);
}
inline void maddto(ll &x, ll y) {x += y; if (x > mod) x -= mod;}
inline ll msub(ll x, ll y) {x -= y; if (x < 0) x += mod; return x;}
inline ll mmul(ll x, ll y) {x *= y; x %= mod; return x;}
ll N, M, K;
ll DNA[4][maxN][maxN];
ll corr[256];
char buf;
ll w[maxN], sumW;
ll columnSum[4][maxN];
int main() {
corr[(ll)'A'] = 0;
corr[(ll)'C'] = 1;
corr[(ll)'G'] = 2;
corr[(ll)'T'] = 3;
scanf("%lld %lld %lld", &N, &M, &K);
K = M - K;
for (ll i = 1; i <= N; i++) {
for (ll j = 1; j <= M; j++) {
scanf(" %c", &buf);
DNA[corr[(ll)buf]][i][j] = 1;
}
w[i] = getRand(1, maxW);
maddto(sumW, w[i]);
}
for (ll j = 1; j <= M; j++) {
for (ll d = 0; d < 4; d++) {
for (ll i = 1; i <= N; i++) {
maddto(columnSum[d][j], w[i] * DNA[d][i][j]);
}
}
}
for (ll comp = 1; comp <= N; comp++) {
ll target = mmul(K, msub(sumW, w[comp]));
ll total = 0;
for (ll d = 0; d < 4; d++) {
for (ll col = 1; col <= M; col++) {
maddto(total, mmul(DNA[d][comp][col], msub(columnSum[d][col], mmul(w[comp], DNA[d][comp][col]))));
}
}
if (target == total) {
printf("%lld\n", comp);
return 0;
}
}
}
Compilation message
genetics.cpp: In function 'int main()':
genetics.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%lld %lld %lld", &N, &M, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf(" %c", &buf);
| ~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
2 ms |
2132 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
1236 KB |
Output is correct |
5 |
Correct |
2 ms |
1876 KB |
Output is correct |
6 |
Correct |
2 ms |
1108 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
1348 KB |
Output is correct |
10 |
Correct |
2 ms |
2004 KB |
Output is correct |
11 |
Correct |
2 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
2132 KB |
Output is correct |
13 |
Correct |
2 ms |
1236 KB |
Output is correct |
14 |
Correct |
2 ms |
1748 KB |
Output is correct |
15 |
Correct |
2 ms |
2260 KB |
Output is correct |
16 |
Correct |
1 ms |
1492 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
272 ms |
53616 KB |
Output is correct |
2 |
Correct |
330 ms |
65840 KB |
Output is correct |
3 |
Correct |
325 ms |
62892 KB |
Output is correct |
4 |
Correct |
70 ms |
20268 KB |
Output is correct |
5 |
Correct |
289 ms |
65768 KB |
Output is correct |
6 |
Correct |
305 ms |
65892 KB |
Output is correct |
7 |
Correct |
143 ms |
28148 KB |
Output is correct |
8 |
Correct |
140 ms |
28108 KB |
Output is correct |
9 |
Correct |
265 ms |
61316 KB |
Output is correct |
10 |
Correct |
306 ms |
61400 KB |
Output is correct |
11 |
Correct |
254 ms |
53688 KB |
Output is correct |
12 |
Correct |
232 ms |
54028 KB |
Output is correct |
13 |
Correct |
243 ms |
53784 KB |
Output is correct |
14 |
Correct |
229 ms |
45980 KB |
Output is correct |
15 |
Correct |
209 ms |
46680 KB |
Output is correct |
16 |
Correct |
208 ms |
47936 KB |
Output is correct |
17 |
Correct |
304 ms |
63188 KB |
Output is correct |
18 |
Correct |
272 ms |
62596 KB |
Output is correct |
19 |
Correct |
297 ms |
63120 KB |
Output is correct |
20 |
Correct |
274 ms |
62244 KB |
Output is correct |
21 |
Correct |
317 ms |
63156 KB |
Output is correct |
22 |
Correct |
335 ms |
62520 KB |
Output is correct |
23 |
Correct |
325 ms |
62768 KB |
Output is correct |
24 |
Correct |
327 ms |
62840 KB |
Output is correct |
25 |
Correct |
291 ms |
62348 KB |
Output is correct |
26 |
Correct |
287 ms |
62756 KB |
Output is correct |
27 |
Correct |
291 ms |
62396 KB |
Output is correct |
28 |
Correct |
287 ms |
62316 KB |
Output is correct |
29 |
Correct |
308 ms |
62788 KB |
Output is correct |
30 |
Correct |
297 ms |
65788 KB |
Output is correct |
31 |
Correct |
316 ms |
65848 KB |
Output is correct |
32 |
Correct |
302 ms |
65848 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
2 ms |
1236 KB |
Output is correct |
35 |
Correct |
0 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
272 ms |
53616 KB |
Output is correct |
2 |
Correct |
330 ms |
65840 KB |
Output is correct |
3 |
Correct |
325 ms |
62892 KB |
Output is correct |
4 |
Correct |
70 ms |
20268 KB |
Output is correct |
5 |
Correct |
289 ms |
65768 KB |
Output is correct |
6 |
Correct |
305 ms |
65892 KB |
Output is correct |
7 |
Correct |
143 ms |
28148 KB |
Output is correct |
8 |
Correct |
140 ms |
28108 KB |
Output is correct |
9 |
Correct |
265 ms |
61316 KB |
Output is correct |
10 |
Correct |
306 ms |
61400 KB |
Output is correct |
11 |
Correct |
254 ms |
53688 KB |
Output is correct |
12 |
Correct |
232 ms |
54028 KB |
Output is correct |
13 |
Correct |
243 ms |
53784 KB |
Output is correct |
14 |
Correct |
229 ms |
45980 KB |
Output is correct |
15 |
Correct |
209 ms |
46680 KB |
Output is correct |
16 |
Correct |
208 ms |
47936 KB |
Output is correct |
17 |
Correct |
304 ms |
63188 KB |
Output is correct |
18 |
Correct |
272 ms |
62596 KB |
Output is correct |
19 |
Correct |
297 ms |
63120 KB |
Output is correct |
20 |
Correct |
274 ms |
62244 KB |
Output is correct |
21 |
Correct |
317 ms |
63156 KB |
Output is correct |
22 |
Correct |
335 ms |
62520 KB |
Output is correct |
23 |
Correct |
325 ms |
62768 KB |
Output is correct |
24 |
Correct |
327 ms |
62840 KB |
Output is correct |
25 |
Correct |
291 ms |
62348 KB |
Output is correct |
26 |
Correct |
287 ms |
62756 KB |
Output is correct |
27 |
Correct |
291 ms |
62396 KB |
Output is correct |
28 |
Correct |
287 ms |
62316 KB |
Output is correct |
29 |
Correct |
308 ms |
62788 KB |
Output is correct |
30 |
Correct |
297 ms |
65788 KB |
Output is correct |
31 |
Correct |
316 ms |
65848 KB |
Output is correct |
32 |
Correct |
302 ms |
65848 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
2 ms |
1236 KB |
Output is correct |
35 |
Correct |
0 ms |
468 KB |
Output is correct |
36 |
Correct |
1434 ms |
231432 KB |
Output is correct |
37 |
Correct |
1584 ms |
265868 KB |
Output is correct |
38 |
Correct |
1714 ms |
260372 KB |
Output is correct |
39 |
Correct |
597 ms |
124276 KB |
Output is correct |
40 |
Correct |
1643 ms |
265540 KB |
Output is correct |
41 |
Correct |
860 ms |
134448 KB |
Output is correct |
42 |
Correct |
801 ms |
134444 KB |
Output is correct |
43 |
Correct |
1149 ms |
217572 KB |
Output is correct |
44 |
Correct |
1576 ms |
265776 KB |
Output is correct |
45 |
Correct |
1631 ms |
265924 KB |
Output is correct |
46 |
Correct |
1521 ms |
265784 KB |
Output is correct |
47 |
Correct |
1432 ms |
233388 KB |
Output is correct |
48 |
Correct |
1508 ms |
233336 KB |
Output is correct |
49 |
Correct |
1138 ms |
200284 KB |
Output is correct |
50 |
Correct |
1275 ms |
200236 KB |
Output is correct |
51 |
Correct |
1391 ms |
225008 KB |
Output is correct |
52 |
Correct |
1672 ms |
259580 KB |
Output is correct |
53 |
Correct |
1703 ms |
259524 KB |
Output is correct |
54 |
Correct |
1441 ms |
259872 KB |
Output is correct |
55 |
Correct |
1613 ms |
259968 KB |
Output is correct |
56 |
Correct |
1435 ms |
260096 KB |
Output is correct |
57 |
Correct |
1697 ms |
260676 KB |
Output is correct |
58 |
Correct |
1542 ms |
260772 KB |
Output is correct |
59 |
Correct |
1512 ms |
259280 KB |
Output is correct |
60 |
Correct |
1486 ms |
260912 KB |
Output is correct |
61 |
Correct |
1540 ms |
259324 KB |
Output is correct |
62 |
Correct |
1461 ms |
258288 KB |
Output is correct |
63 |
Correct |
1448 ms |
260512 KB |
Output is correct |
64 |
Correct |
1481 ms |
260588 KB |
Output is correct |
65 |
Correct |
1651 ms |
259576 KB |
Output is correct |
66 |
Correct |
1633 ms |
273488 KB |
Output is correct |
67 |
Correct |
1643 ms |
274412 KB |
Output is correct |
68 |
Correct |
1571 ms |
274292 KB |
Output is correct |
69 |
Correct |
1465 ms |
272872 KB |
Output is correct |
70 |
Correct |
1614 ms |
273980 KB |
Output is correct |
71 |
Correct |
1555 ms |
272756 KB |
Output is correct |
72 |
Correct |
1580 ms |
274952 KB |
Output is correct |
73 |
Correct |
1615 ms |
273216 KB |
Output is correct |
74 |
Correct |
1 ms |
340 KB |
Output is correct |
75 |
Correct |
2 ms |
1220 KB |
Output is correct |
76 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
2 ms |
2132 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
1236 KB |
Output is correct |
5 |
Correct |
2 ms |
1876 KB |
Output is correct |
6 |
Correct |
2 ms |
1108 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
1348 KB |
Output is correct |
10 |
Correct |
2 ms |
2004 KB |
Output is correct |
11 |
Correct |
2 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
2132 KB |
Output is correct |
13 |
Correct |
2 ms |
1236 KB |
Output is correct |
14 |
Correct |
2 ms |
1748 KB |
Output is correct |
15 |
Correct |
2 ms |
2260 KB |
Output is correct |
16 |
Correct |
1 ms |
1492 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
272 ms |
53616 KB |
Output is correct |
19 |
Correct |
330 ms |
65840 KB |
Output is correct |
20 |
Correct |
325 ms |
62892 KB |
Output is correct |
21 |
Correct |
70 ms |
20268 KB |
Output is correct |
22 |
Correct |
289 ms |
65768 KB |
Output is correct |
23 |
Correct |
305 ms |
65892 KB |
Output is correct |
24 |
Correct |
143 ms |
28148 KB |
Output is correct |
25 |
Correct |
140 ms |
28108 KB |
Output is correct |
26 |
Correct |
265 ms |
61316 KB |
Output is correct |
27 |
Correct |
306 ms |
61400 KB |
Output is correct |
28 |
Correct |
254 ms |
53688 KB |
Output is correct |
29 |
Correct |
232 ms |
54028 KB |
Output is correct |
30 |
Correct |
243 ms |
53784 KB |
Output is correct |
31 |
Correct |
229 ms |
45980 KB |
Output is correct |
32 |
Correct |
209 ms |
46680 KB |
Output is correct |
33 |
Correct |
208 ms |
47936 KB |
Output is correct |
34 |
Correct |
304 ms |
63188 KB |
Output is correct |
35 |
Correct |
272 ms |
62596 KB |
Output is correct |
36 |
Correct |
297 ms |
63120 KB |
Output is correct |
37 |
Correct |
274 ms |
62244 KB |
Output is correct |
38 |
Correct |
317 ms |
63156 KB |
Output is correct |
39 |
Correct |
335 ms |
62520 KB |
Output is correct |
40 |
Correct |
325 ms |
62768 KB |
Output is correct |
41 |
Correct |
327 ms |
62840 KB |
Output is correct |
42 |
Correct |
291 ms |
62348 KB |
Output is correct |
43 |
Correct |
287 ms |
62756 KB |
Output is correct |
44 |
Correct |
291 ms |
62396 KB |
Output is correct |
45 |
Correct |
287 ms |
62316 KB |
Output is correct |
46 |
Correct |
308 ms |
62788 KB |
Output is correct |
47 |
Correct |
297 ms |
65788 KB |
Output is correct |
48 |
Correct |
316 ms |
65848 KB |
Output is correct |
49 |
Correct |
302 ms |
65848 KB |
Output is correct |
50 |
Correct |
1 ms |
340 KB |
Output is correct |
51 |
Correct |
2 ms |
1236 KB |
Output is correct |
52 |
Correct |
0 ms |
468 KB |
Output is correct |
53 |
Correct |
1434 ms |
231432 KB |
Output is correct |
54 |
Correct |
1584 ms |
265868 KB |
Output is correct |
55 |
Correct |
1714 ms |
260372 KB |
Output is correct |
56 |
Correct |
597 ms |
124276 KB |
Output is correct |
57 |
Correct |
1643 ms |
265540 KB |
Output is correct |
58 |
Correct |
860 ms |
134448 KB |
Output is correct |
59 |
Correct |
801 ms |
134444 KB |
Output is correct |
60 |
Correct |
1149 ms |
217572 KB |
Output is correct |
61 |
Correct |
1576 ms |
265776 KB |
Output is correct |
62 |
Correct |
1631 ms |
265924 KB |
Output is correct |
63 |
Correct |
1521 ms |
265784 KB |
Output is correct |
64 |
Correct |
1432 ms |
233388 KB |
Output is correct |
65 |
Correct |
1508 ms |
233336 KB |
Output is correct |
66 |
Correct |
1138 ms |
200284 KB |
Output is correct |
67 |
Correct |
1275 ms |
200236 KB |
Output is correct |
68 |
Correct |
1391 ms |
225008 KB |
Output is correct |
69 |
Correct |
1672 ms |
259580 KB |
Output is correct |
70 |
Correct |
1703 ms |
259524 KB |
Output is correct |
71 |
Correct |
1441 ms |
259872 KB |
Output is correct |
72 |
Correct |
1613 ms |
259968 KB |
Output is correct |
73 |
Correct |
1435 ms |
260096 KB |
Output is correct |
74 |
Correct |
1697 ms |
260676 KB |
Output is correct |
75 |
Correct |
1542 ms |
260772 KB |
Output is correct |
76 |
Correct |
1512 ms |
259280 KB |
Output is correct |
77 |
Correct |
1486 ms |
260912 KB |
Output is correct |
78 |
Correct |
1540 ms |
259324 KB |
Output is correct |
79 |
Correct |
1461 ms |
258288 KB |
Output is correct |
80 |
Correct |
1448 ms |
260512 KB |
Output is correct |
81 |
Correct |
1481 ms |
260588 KB |
Output is correct |
82 |
Correct |
1651 ms |
259576 KB |
Output is correct |
83 |
Correct |
1633 ms |
273488 KB |
Output is correct |
84 |
Correct |
1643 ms |
274412 KB |
Output is correct |
85 |
Correct |
1571 ms |
274292 KB |
Output is correct |
86 |
Correct |
1465 ms |
272872 KB |
Output is correct |
87 |
Correct |
1614 ms |
273980 KB |
Output is correct |
88 |
Correct |
1555 ms |
272756 KB |
Output is correct |
89 |
Correct |
1580 ms |
274952 KB |
Output is correct |
90 |
Correct |
1615 ms |
273216 KB |
Output is correct |
91 |
Correct |
1 ms |
340 KB |
Output is correct |
92 |
Correct |
2 ms |
1220 KB |
Output is correct |
93 |
Correct |
1 ms |
468 KB |
Output is correct |
94 |
Correct |
1643 ms |
513980 KB |
Output is correct |
95 |
Correct |
1818 ms |
543256 KB |
Output is correct |
96 |
Correct |
1900 ms |
533852 KB |
Output is correct |
97 |
Correct |
1041 ms |
290264 KB |
Output is correct |
98 |
Correct |
651 ms |
187840 KB |
Output is correct |
99 |
Correct |
1745 ms |
280404 KB |
Output is correct |
100 |
Correct |
916 ms |
271656 KB |
Output is correct |
101 |
Correct |
901 ms |
271636 KB |
Output is correct |
102 |
Correct |
1235 ms |
440760 KB |
Output is correct |
103 |
Correct |
1577 ms |
280548 KB |
Output is correct |
104 |
Correct |
1869 ms |
542952 KB |
Output is correct |
105 |
Correct |
1946 ms |
542920 KB |
Output is correct |
106 |
Correct |
1776 ms |
515712 KB |
Output is correct |
107 |
Correct |
1380 ms |
245500 KB |
Output is correct |
108 |
Correct |
1313 ms |
210504 KB |
Output is correct |
109 |
Correct |
1540 ms |
468428 KB |
Output is correct |
110 |
Correct |
1584 ms |
458056 KB |
Output is correct |
111 |
Correct |
1820 ms |
411856 KB |
Output is correct |
112 |
Correct |
1785 ms |
536108 KB |
Output is correct |
113 |
Correct |
1830 ms |
529776 KB |
Output is correct |
114 |
Correct |
1460 ms |
273516 KB |
Output is correct |
115 |
Correct |
1827 ms |
529860 KB |
Output is correct |
116 |
Correct |
1818 ms |
535684 KB |
Output is correct |
117 |
Correct |
1843 ms |
537012 KB |
Output is correct |
118 |
Correct |
1793 ms |
536348 KB |
Output is correct |
119 |
Correct |
1787 ms |
534480 KB |
Output is correct |
120 |
Correct |
1829 ms |
536528 KB |
Output is correct |
121 |
Correct |
1454 ms |
245576 KB |
Output is correct |
122 |
Correct |
1626 ms |
280712 KB |
Output is correct |
123 |
Correct |
1761 ms |
273972 KB |
Output is correct |
124 |
Correct |
0 ms |
312 KB |
Output is correct |
125 |
Correct |
2 ms |
1224 KB |
Output is correct |
126 |
Correct |
1 ms |
340 KB |
Output is correct |