#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
static void run_with_stack_size(void (*func)(void), size_t stsize) {
char *stack, *send;
stack = (char *)malloc(stsize);
send = stack + stsize - 16;
send = (char *)((uintptr_t)send / 16 * 16);
asm volatile(
"mov %%rsp, (%0)\n"
"mov %0, %%rsp\n"
:
: "r"(send));
func();
asm volatile("mov (%0), %%rsp\n" : : "r"(send));
free(stack);
}
void solve(int tc) {
int n, m;
cin >> n >> m;
int k;
cin >> k;
int a[m], c[m], g[m], t[m];
for(int i=0; i<m; i++) {
a[i] = c[i] = g[i] = t[i] = 0;
}
string s[n];
for(int i=0; i<n; i++) {
cin >> s[i];
for(int j=0; j<m; j++) s[i][j] ^= 32;
for(int j=0; j<m; j++) {
if(s[i][j] == 'a') a[j]++;
else if(s[i][j] == 'c') c[j]++;
else if(s[i][j] == 'g') g[j]++;
else t[j]++;
}
}
bool banned[n];
for(int i=0; i<n; i++) banned[i] = 0;
for(int i=0; i<n; i++) {
if(banned[i]) continue;
int totn = 0;
for(int j=0; j<m; j++) {
if(s[i][j] == 'a') totn += c[j] + g[j] + t[j];
else if(s[i][j] == 'c') totn += a[j] + g[j] + t[j];
else if(s[i][j] == 'g') totn += a[j] + c[j] + t[j];
else totn += a[j] + c[j] + g[j];
}
if(totn == k * (n - 1)) {
bool can = 1;
for(int j=0; j<n; j++) {
if(i != j) {
int cnt = 0;
for(int l=0; l<m; l++) cnt += (s[i][l] != s[j][l]);
if(cnt != k) {
can = 0;
banned[j] = 1;
}
}
}
if(can) {
cout << i+1 << '\n'; return;
}
else banned[i] = 1;
}
}
}
void uwu() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
int32_t main() {
#ifdef ONLINE_JUDGE
uwu();
#endif
#ifndef ONLINE_JUDGE
run_with_stack_size(uwu, 1024 * 1024 * 1024); // run with a 1 GiB stack
#endif
}
/*
g++ B.cpp -std=c++17 -O2 -o B
./B < input.txt
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
600 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
560 ms |
3320 KB |
Output is correct |
2 |
Correct |
17 ms |
3928 KB |
Output is correct |
3 |
Correct |
38 ms |
4048 KB |
Output is correct |
4 |
Correct |
8 ms |
1116 KB |
Output is correct |
5 |
Correct |
26 ms |
3960 KB |
Output is correct |
6 |
Correct |
30 ms |
3932 KB |
Output is correct |
7 |
Correct |
16 ms |
2052 KB |
Output is correct |
8 |
Correct |
14 ms |
1884 KB |
Output is correct |
9 |
Correct |
30 ms |
3708 KB |
Output is correct |
10 |
Correct |
465 ms |
3720 KB |
Output is correct |
11 |
Correct |
388 ms |
3164 KB |
Output is correct |
12 |
Correct |
63 ms |
3164 KB |
Output is correct |
13 |
Correct |
187 ms |
5364 KB |
Output is correct |
14 |
Correct |
320 ms |
2904 KB |
Output is correct |
15 |
Correct |
75 ms |
2964 KB |
Output is correct |
16 |
Correct |
20 ms |
2908 KB |
Output is correct |
17 |
Correct |
34 ms |
3788 KB |
Output is correct |
18 |
Correct |
23 ms |
3664 KB |
Output is correct |
19 |
Correct |
33 ms |
5720 KB |
Output is correct |
20 |
Correct |
26 ms |
5724 KB |
Output is correct |
21 |
Correct |
32 ms |
3672 KB |
Output is correct |
22 |
Correct |
36 ms |
5720 KB |
Output is correct |
23 |
Correct |
37 ms |
3676 KB |
Output is correct |
24 |
Correct |
37 ms |
3928 KB |
Output is correct |
25 |
Correct |
26 ms |
3664 KB |
Output is correct |
26 |
Correct |
29 ms |
3676 KB |
Output is correct |
27 |
Correct |
28 ms |
3672 KB |
Output is correct |
28 |
Correct |
28 ms |
3676 KB |
Output is correct |
29 |
Correct |
34 ms |
3676 KB |
Output is correct |
30 |
Correct |
16 ms |
4028 KB |
Output is correct |
31 |
Correct |
19 ms |
3932 KB |
Output is correct |
32 |
Correct |
28 ms |
3932 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
560 ms |
3320 KB |
Output is correct |
2 |
Correct |
17 ms |
3928 KB |
Output is correct |
3 |
Correct |
38 ms |
4048 KB |
Output is correct |
4 |
Correct |
8 ms |
1116 KB |
Output is correct |
5 |
Correct |
26 ms |
3960 KB |
Output is correct |
6 |
Correct |
30 ms |
3932 KB |
Output is correct |
7 |
Correct |
16 ms |
2052 KB |
Output is correct |
8 |
Correct |
14 ms |
1884 KB |
Output is correct |
9 |
Correct |
30 ms |
3708 KB |
Output is correct |
10 |
Correct |
465 ms |
3720 KB |
Output is correct |
11 |
Correct |
388 ms |
3164 KB |
Output is correct |
12 |
Correct |
63 ms |
3164 KB |
Output is correct |
13 |
Correct |
187 ms |
5364 KB |
Output is correct |
14 |
Correct |
320 ms |
2904 KB |
Output is correct |
15 |
Correct |
75 ms |
2964 KB |
Output is correct |
16 |
Correct |
20 ms |
2908 KB |
Output is correct |
17 |
Correct |
34 ms |
3788 KB |
Output is correct |
18 |
Correct |
23 ms |
3664 KB |
Output is correct |
19 |
Correct |
33 ms |
5720 KB |
Output is correct |
20 |
Correct |
26 ms |
5724 KB |
Output is correct |
21 |
Correct |
32 ms |
3672 KB |
Output is correct |
22 |
Correct |
36 ms |
5720 KB |
Output is correct |
23 |
Correct |
37 ms |
3676 KB |
Output is correct |
24 |
Correct |
37 ms |
3928 KB |
Output is correct |
25 |
Correct |
26 ms |
3664 KB |
Output is correct |
26 |
Correct |
29 ms |
3676 KB |
Output is correct |
27 |
Correct |
28 ms |
3672 KB |
Output is correct |
28 |
Correct |
28 ms |
3676 KB |
Output is correct |
29 |
Correct |
34 ms |
3676 KB |
Output is correct |
30 |
Correct |
16 ms |
4028 KB |
Output is correct |
31 |
Correct |
19 ms |
3932 KB |
Output is correct |
32 |
Correct |
28 ms |
3932 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Execution timed out |
2041 ms |
17624 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
600 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
560 ms |
3320 KB |
Output is correct |
19 |
Correct |
17 ms |
3928 KB |
Output is correct |
20 |
Correct |
38 ms |
4048 KB |
Output is correct |
21 |
Correct |
8 ms |
1116 KB |
Output is correct |
22 |
Correct |
26 ms |
3960 KB |
Output is correct |
23 |
Correct |
30 ms |
3932 KB |
Output is correct |
24 |
Correct |
16 ms |
2052 KB |
Output is correct |
25 |
Correct |
14 ms |
1884 KB |
Output is correct |
26 |
Correct |
30 ms |
3708 KB |
Output is correct |
27 |
Correct |
465 ms |
3720 KB |
Output is correct |
28 |
Correct |
388 ms |
3164 KB |
Output is correct |
29 |
Correct |
63 ms |
3164 KB |
Output is correct |
30 |
Correct |
187 ms |
5364 KB |
Output is correct |
31 |
Correct |
320 ms |
2904 KB |
Output is correct |
32 |
Correct |
75 ms |
2964 KB |
Output is correct |
33 |
Correct |
20 ms |
2908 KB |
Output is correct |
34 |
Correct |
34 ms |
3788 KB |
Output is correct |
35 |
Correct |
23 ms |
3664 KB |
Output is correct |
36 |
Correct |
33 ms |
5720 KB |
Output is correct |
37 |
Correct |
26 ms |
5724 KB |
Output is correct |
38 |
Correct |
32 ms |
3672 KB |
Output is correct |
39 |
Correct |
36 ms |
5720 KB |
Output is correct |
40 |
Correct |
37 ms |
3676 KB |
Output is correct |
41 |
Correct |
37 ms |
3928 KB |
Output is correct |
42 |
Correct |
26 ms |
3664 KB |
Output is correct |
43 |
Correct |
29 ms |
3676 KB |
Output is correct |
44 |
Correct |
28 ms |
3672 KB |
Output is correct |
45 |
Correct |
28 ms |
3676 KB |
Output is correct |
46 |
Correct |
34 ms |
3676 KB |
Output is correct |
47 |
Correct |
16 ms |
4028 KB |
Output is correct |
48 |
Correct |
19 ms |
3932 KB |
Output is correct |
49 |
Correct |
28 ms |
3932 KB |
Output is correct |
50 |
Correct |
1 ms |
348 KB |
Output is correct |
51 |
Correct |
0 ms |
348 KB |
Output is correct |
52 |
Correct |
0 ms |
348 KB |
Output is correct |
53 |
Execution timed out |
2041 ms |
17624 KB |
Time limit exceeded |
54 |
Halted |
0 ms |
0 KB |
- |