oj.uz

Submission #404215

# Submission time Handle Problem Language Result Execution time Memory
404215 2021-05-14T00:47:13 Z rama_pang Genetics (BOI18_genetics) C++17
100 / 100
 526 ms 25348 KB 
#include <bits/stdc++.h>
using namespace std;

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

  int N, M, K;
  cin >> N >> M >> K;

  const int MAX = 16405;
  vector<bitset<MAX>> A(N, 0);

  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < M; j++) {
      if (s[j] == 'A') A[i][j * 4 + 0] = 1;
      if (s[j] == 'C') A[i][j * 4 + 1] = 1;
      if (s[j] == 'T') A[i][j * 4 + 2] = 1;
      if (s[j] == 'G') A[i][j * 4 + 3] = 1;
    }
  }

  // Turn input into binary string
  M = 4 * M;
  K = 2 * K;

  // bit 0 = -1
  // bit 1 = +1
  // Take \sum A[x][i] * A[y][i]
  // (M - K) - K = differ
  // differ = M - 2K
  K = M - 2 * K;

  mt19937 rnd(123456789);
  vector<int> weight(N);
  for (int i = 0; i < N; i++) {
    weight[i] = (rnd()) % (1ll << 30);
  }

  long long sum_weight = 0;
  vector<long long> sum(M);
  for (int i = 0; i < N; i++) {
    sum_weight += weight[i];
    for (int j = 0; j < M; j++) {
      sum[j] += (A[i][j] == 0 ? -1 : 1) * weight[i];
    }
  }

  for (int i = 0; i < N; i++) {
    long long hashed = 0;
    for (int j = 0; j < M; j++) {
      int sgn = (A[i][j] == 0 ? -1 : 1);
      hashed += 1ll * sgn * (sum[j] - sgn * weight[i]);
    }
    long long should_be = 1ll * (sum_weight - weight[i]) * K;
    if (hashed == should_be) {
      cout << i + 1 << '\n';
      return 0;
    }
  }

  cout << -1 << '\n';
  return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 332 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3404 KB Output is correct
2 Correct 67 ms 7256 KB Output is correct
3 Correct 77 ms 6872 KB Output is correct
4 Correct 21 ms 3324 KB Output is correct
5 Correct 49 ms 7164 KB Output is correct
6 Correct 58 ms 7108 KB Output is correct
7 Correct 33 ms 3288 KB Output is correct
8 Correct 30 ms 3276 KB Output is correct
9 Correct 45 ms 6764 KB Output is correct
10 Correct 67 ms 6724 KB Output is correct
11 Correct 53 ms 5936 KB Output is correct
12 Correct 38 ms 5972 KB Output is correct
13 Correct 45 ms 5952 KB Output is correct
14 Correct 54 ms 5144 KB Output is correct
15 Correct 37 ms 5264 KB Output is correct
16 Correct 39 ms 5488 KB Output is correct
17 Correct 69 ms 6872 KB Output is correct
18 Correct 53 ms 6848 KB Output is correct
19 Correct 65 ms 6852 KB Output is correct
20 Correct 49 ms 6724 KB Output is correct
21 Correct 65 ms 6880 KB Output is correct
22 Correct 74 ms 6724 KB Output is correct
23 Correct 76 ms 6868 KB Output is correct
24 Correct 74 ms 6852 KB Output is correct
25 Correct 51 ms 6704 KB Output is correct
26 Correct 58 ms 6860 KB Output is correct
27 Correct 55 ms 6728 KB Output is correct
28 Correct 55 ms 6724 KB Output is correct
29 Correct 68 ms 6856 KB Output is correct
30 Correct 40 ms 7108 KB Output is correct
31 Correct 54 ms 7112 KB Output is correct
32 Correct 56 ms 7172 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 1 ms 332 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3404 KB Output is correct
2 Correct 67 ms 7256 KB Output is correct
3 Correct 77 ms 6872 KB Output is correct
4 Correct 21 ms 3324 KB Output is correct
5 Correct 49 ms 7164 KB Output is correct
6 Correct 58 ms 7108 KB Output is correct
7 Correct 33 ms 3288 KB Output is correct
8 Correct 30 ms 3276 KB Output is correct
9 Correct 45 ms 6764 KB Output is correct
10 Correct 67 ms 6724 KB Output is correct
11 Correct 53 ms 5936 KB Output is correct
12 Correct 38 ms 5972 KB Output is correct
13 Correct 45 ms 5952 KB Output is correct
14 Correct 54 ms 5144 KB Output is correct
15 Correct 37 ms 5264 KB Output is correct
16 Correct 39 ms 5488 KB Output is correct
17 Correct 69 ms 6872 KB Output is correct
18 Correct 53 ms 6848 KB Output is correct
19 Correct 65 ms 6852 KB Output is correct
20 Correct 49 ms 6724 KB Output is correct
21 Correct 65 ms 6880 KB Output is correct
22 Correct 74 ms 6724 KB Output is correct
23 Correct 76 ms 6868 KB Output is correct
24 Correct 74 ms 6852 KB Output is correct
25 Correct 51 ms 6704 KB Output is correct
26 Correct 58 ms 6860 KB Output is correct
27 Correct 55 ms 6728 KB Output is correct
28 Correct 55 ms 6724 KB Output is correct
29 Correct 68 ms 6856 KB Output is correct
30 Correct 40 ms 7108 KB Output is correct
31 Correct 54 ms 7112 KB Output is correct
32 Correct 56 ms 7172 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 286 ms 22148 KB Output is correct
37 Correct 232 ms 25156 KB Output is correct
38 Correct 385 ms 24648 KB Output is correct
39 Correct 114 ms 13124 KB Output is correct
40 Correct 328 ms 25152 KB Output is correct
41 Correct 170 ms 12820 KB Output is correct
42 Correct 151 ms 12904 KB Output is correct
43 Correct 187 ms 19076 KB Output is correct
44 Correct 244 ms 25244 KB Output is correct
45 Correct 340 ms 25160 KB Output is correct
46 Correct 239 ms 25160 KB Output is correct
47 Correct 282 ms 22084 KB Output is correct
48 Correct 332 ms 22104 KB Output is correct
49 Correct 189 ms 18912 KB Output is correct
50 Correct 275 ms 18996 KB Output is correct
51 Correct 314 ms 21316 KB Output is correct
52 Correct 364 ms 24604 KB Output is correct
53 Correct 371 ms 24544 KB Output is correct
54 Correct 187 ms 24152 KB Output is correct
55 Correct 298 ms 24196 KB Output is correct
56 Correct 242 ms 24160 KB Output is correct
57 Correct 389 ms 24624 KB Output is correct
58 Correct 311 ms 24512 KB Output is correct
59 Correct 276 ms 24492 KB Output is correct
60 Correct 292 ms 24516 KB Output is correct
61 Correct 269 ms 24468 KB Output is correct
62 Correct 256 ms 24388 KB Output is correct
63 Correct 236 ms 24500 KB Output is correct
64 Correct 265 ms 24592 KB Output is correct
65 Correct 364 ms 24592 KB Output is correct
66 Correct 363 ms 24536 KB Output is correct
67 Correct 348 ms 24632 KB Output is correct
68 Correct 303 ms 24520 KB Output is correct
69 Correct 228 ms 24500 KB Output is correct
70 Correct 351 ms 24480 KB Output is correct
71 Correct 295 ms 24496 KB Output is correct
72 Correct 333 ms 24784 KB Output is correct
73 Correct 331 ms 24468 KB Output is correct
74 Correct 1 ms 332 KB Output is correct
75 Correct 1 ms 460 KB Output is correct
76 Correct 1 ms 320 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 62 ms 3404 KB Output is correct
19 Correct 67 ms 7256 KB Output is correct
20 Correct 77 ms 6872 KB Output is correct
21 Correct 21 ms 3324 KB Output is correct
22 Correct 49 ms 7164 KB Output is correct
23 Correct 58 ms 7108 KB Output is correct
24 Correct 33 ms 3288 KB Output is correct
25 Correct 30 ms 3276 KB Output is correct
26 Correct 45 ms 6764 KB Output is correct
27 Correct 67 ms 6724 KB Output is correct
28 Correct 53 ms 5936 KB Output is correct
29 Correct 38 ms 5972 KB Output is correct
30 Correct 45 ms 5952 KB Output is correct
31 Correct 54 ms 5144 KB Output is correct
32 Correct 37 ms 5264 KB Output is correct
33 Correct 39 ms 5488 KB Output is correct
34 Correct 69 ms 6872 KB Output is correct
35 Correct 53 ms 6848 KB Output is correct
36 Correct 65 ms 6852 KB Output is correct
37 Correct 49 ms 6724 KB Output is correct
38 Correct 65 ms 6880 KB Output is correct
39 Correct 74 ms 6724 KB Output is correct
40 Correct 76 ms 6868 KB Output is correct
41 Correct 74 ms 6852 KB Output is correct
42 Correct 51 ms 6704 KB Output is correct
43 Correct 58 ms 6860 KB Output is correct
44 Correct 55 ms 6728 KB Output is correct
45 Correct 55 ms 6724 KB Output is correct
46 Correct 68 ms 6856 KB Output is correct
47 Correct 40 ms 7108 KB Output is correct
48 Correct 54 ms 7112 KB Output is correct
49 Correct 56 ms 7172 KB Output is correct
50 Correct 1 ms 332 KB Output is correct
51 Correct 1 ms 460 KB Output is correct
52 Correct 1 ms 332 KB Output is correct
53 Correct 286 ms 22148 KB Output is correct
54 Correct 232 ms 25156 KB Output is correct
55 Correct 385 ms 24648 KB Output is correct
56 Correct 114 ms 13124 KB Output is correct
57 Correct 328 ms 25152 KB Output is correct
58 Correct 170 ms 12820 KB Output is correct
59 Correct 151 ms 12904 KB Output is correct
60 Correct 187 ms 19076 KB Output is correct
61 Correct 244 ms 25244 KB Output is correct
62 Correct 340 ms 25160 KB Output is correct
63 Correct 239 ms 25160 KB Output is correct
64 Correct 282 ms 22084 KB Output is correct
65 Correct 332 ms 22104 KB Output is correct
66 Correct 189 ms 18912 KB Output is correct
67 Correct 275 ms 18996 KB Output is correct
68 Correct 314 ms 21316 KB Output is correct
69 Correct 364 ms 24604 KB Output is correct
70 Correct 371 ms 24544 KB Output is correct
71 Correct 187 ms 24152 KB Output is correct
72 Correct 298 ms 24196 KB Output is correct
73 Correct 242 ms 24160 KB Output is correct
74 Correct 389 ms 24624 KB Output is correct
75 Correct 311 ms 24512 KB Output is correct
76 Correct 276 ms 24492 KB Output is correct
77 Correct 292 ms 24516 KB Output is correct
78 Correct 269 ms 24468 KB Output is correct
79 Correct 256 ms 24388 KB Output is correct
80 Correct 236 ms 24500 KB Output is correct
81 Correct 265 ms 24592 KB Output is correct
82 Correct 364 ms 24592 KB Output is correct
83 Correct 363 ms 24536 KB Output is correct
84 Correct 348 ms 24632 KB Output is correct
85 Correct 303 ms 24520 KB Output is correct
86 Correct 228 ms 24500 KB Output is correct
87 Correct 351 ms 24480 KB Output is correct
88 Correct 295 ms 24496 KB Output is correct
89 Correct 333 ms 24784 KB Output is correct
90 Correct 331 ms 24468 KB Output is correct
91 Correct 1 ms 332 KB Output is correct
92 Correct 1 ms 460 KB Output is correct
93 Correct 1 ms 320 KB Output is correct
94 Correct 270 ms 23784 KB Output is correct
95 Correct 323 ms 25192 KB Output is correct
96 Correct 509 ms 24800 KB Output is correct
97 Correct 281 ms 13676 KB Output is correct
98 Correct 146 ms 13216 KB Output is correct
99 Correct 353 ms 25168 KB Output is correct
100 Correct 213 ms 12872 KB Output is correct
101 Correct 178 ms 13044 KB Output is correct
102 Correct 225 ms 19184 KB Output is correct
103 Correct 293 ms 25280 KB Output is correct
104 Correct 466 ms 25348 KB Output is correct
105 Correct 526 ms 25168 KB Output is correct
106 Correct 467 ms 23912 KB Output is correct
107 Correct 235 ms 21984 KB Output is correct
108 Correct 275 ms 19040 KB Output is correct
109 Correct 346 ms 21696 KB Output is correct
110 Correct 406 ms 21004 KB Output is correct
111 Correct 311 ms 25156 KB Output is correct
112 Correct 412 ms 24904 KB Output is correct
113 Correct 386 ms 24196 KB Output is correct
114 Correct 187 ms 24200 KB Output is correct
115 Correct 431 ms 24156 KB Output is correct
116 Correct 449 ms 24812 KB Output is correct
117 Correct 432 ms 24848 KB Output is correct
118 Correct 428 ms 24856 KB Output is correct
119 Correct 398 ms 24772 KB Output is correct
120 Correct 462 ms 24968 KB Output is correct
121 Correct 276 ms 22120 KB Output is correct
122 Correct 260 ms 25104 KB Output is correct
123 Correct 388 ms 24584 KB Output is correct
124 Correct 1 ms 332 KB Output is correct
125 Correct 1 ms 460 KB Output is correct
126 Correct 1 ms 332 KB Output is correct