oj.uz

Submission #949888

# Submission time Handle Problem Language Result Execution time Memory
949888 2024-03-19T20:20:07 Z fuad27 Genetics (BOI18_genetics) C++17
46 / 100
 2000 ms 104640 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
const int N=4200;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
bitset<N> b[N][2];
int dif[N][N];
int diff(int i, int j) {
  if(dif[i][j]>=0)return dif[i][j];
  return dif[i][j]=((b[i][0]^b[j][0])|(b[i][1]^b[j][1])).count();
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n, m, k;
  cin >> n >> m >> k;
  memset(dif, -1, sizeof dif);
  string a[n];
  for(int i =0 ;i<n;i++) {
    cin >> a[i];
    for(int j =0 ;j<m;j++) {
      if(a[i][j]=='A') {
        b[i][0][j]=b[i][1][j]=1;
      }
      else if(a[i][j]=='C') {
        b[i][0][j]=1;
        b[i][1][j]=0;
      }
      else if(a[i][j]=='G') {
        b[i][0][j]=0;
        b[i][1][j]=1;
      }
    }
  }
  bool check[n];
  memset(check, 0, sizeof check);
  queue<int> que;
  for(int i = 0;i<n;i++)que.push(i);
  while(que.size()>1) {
    int at=que.front();
    que.pop();
    if(check[at])continue;
    int c=rng()%n;
    while(c==at) {
      c=rng()%n;
    }
    if(diff(at, c)!=k) {
      check[at]=check[c]=1;
      continue;
    }
    else que.push(at);
  }
  cout << que.front()+1 << "\n";

}

Subtask #1
27.0 / 27.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 77908 KB Output is correct
2 Correct 622 ms 79084 KB Output is correct
3 Correct 857 ms 78672 KB Output is correct
4 Correct 263 ms 73820 KB Output is correct
5 Correct 621 ms 79188 KB Output is correct
6 Correct 613 ms 79084 KB Output is correct
7 Correct 123 ms 73040 KB Output is correct
8 Correct 115 ms 73248 KB Output is correct
9 Correct 316 ms 78420 KB Output is correct
10 Correct 304 ms 78676 KB Output is correct
11 Correct 508 ms 77804 KB Output is correct
12 Correct 514 ms 77832 KB Output is correct
13 Correct 484 ms 77804 KB Output is correct
14 Correct 427 ms 77040 KB Output is correct
15 Correct 443 ms 77184 KB Output is correct
16 Correct 583 ms 77072 KB Output is correct
17 Correct 822 ms 78812 KB Output is correct
18 Correct 847 ms 78904 KB Output is correct
19 Correct 826 ms 78808 KB Output is correct
20 Correct 846 ms 78720 KB Output is correct
21 Correct 833 ms 78932 KB Output is correct
22 Correct 831 ms 78724 KB Output is correct
23 Correct 831 ms 78772 KB Output is correct
24 Correct 851 ms 78768 KB Output is correct
25 Correct 796 ms 78724 KB Output is correct
26 Correct 821 ms 78928 KB Output is correct
27 Correct 911 ms 78740 KB Output is correct
28 Correct 802 ms 78840 KB Output is correct
29 Correct 863 ms 78932 KB Output is correct
30 Correct 26 ms 78928 KB Output is correct
31 Correct 24 ms 78940 KB Output is correct
32 Correct 34 ms 78932 KB Output is correct
33 Correct 9 ms 70388 KB Output is correct
34 Correct 9 ms 70392 KB Output is correct
35 Correct 9 ms 70236 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 77908 KB Output is correct
2 Correct 622 ms 79084 KB Output is correct
3 Correct 857 ms 78672 KB Output is correct
4 Correct 263 ms 73820 KB Output is correct
5 Correct 621 ms 79188 KB Output is correct
6 Correct 613 ms 79084 KB Output is correct
7 Correct 123 ms 73040 KB Output is correct
8 Correct 115 ms 73248 KB Output is correct
9 Correct 316 ms 78420 KB Output is correct
10 Correct 304 ms 78676 KB Output is correct
11 Correct 508 ms 77804 KB Output is correct
12 Correct 514 ms 77832 KB Output is correct
13 Correct 484 ms 77804 KB Output is correct
14 Correct 427 ms 77040 KB Output is correct
15 Correct 443 ms 77184 KB Output is correct
16 Correct 583 ms 77072 KB Output is correct
17 Correct 822 ms 78812 KB Output is correct
18 Correct 847 ms 78904 KB Output is correct
19 Correct 826 ms 78808 KB Output is correct
20 Correct 846 ms 78720 KB Output is correct
21 Correct 833 ms 78932 KB Output is correct
22 Correct 831 ms 78724 KB Output is correct
23 Correct 831 ms 78772 KB Output is correct
24 Correct 851 ms 78768 KB Output is correct
25 Correct 796 ms 78724 KB Output is correct
26 Correct 821 ms 78928 KB Output is correct
27 Correct 911 ms 78740 KB Output is correct
28 Correct 802 ms 78840 KB Output is correct
29 Correct 863 ms 78932 KB Output is correct
30 Correct 26 ms 78928 KB Output is correct
31 Correct 24 ms 78940 KB Output is correct
32 Correct 34 ms 78932 KB Output is correct
33 Correct 9 ms 70388 KB Output is correct
34 Correct 9 ms 70392 KB Output is correct
35 Correct 9 ms 70236 KB Output is correct
36 Execution timed out 2019 ms 104640 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 70372 KB Output is correct
2 Correct 12 ms 70236 KB Output is correct
3 Correct 10 ms 70236 KB Output is correct
4 Correct 11 ms 70236 KB Output is correct
5 Correct 10 ms 70232 KB Output is correct
6 Correct 10 ms 70236 KB Output is correct
7 Correct 9 ms 70236 KB Output is correct
8 Correct 9 ms 70236 KB Output is correct
9 Correct 11 ms 70236 KB Output is correct
10 Correct 11 ms 70236 KB Output is correct
11 Correct 13 ms 70236 KB Output is correct
12 Correct 12 ms 70236 KB Output is correct
13 Correct 9 ms 70236 KB Output is correct
14 Correct 10 ms 70236 KB Output is correct
15 Correct 10 ms 70236 KB Output is correct
16 Correct 9 ms 70236 KB Output is correct
17 Correct 10 ms 70236 KB Output is correct
18 Correct 492 ms 77908 KB Output is correct
19 Correct 622 ms 79084 KB Output is correct
20 Correct 857 ms 78672 KB Output is correct
21 Correct 263 ms 73820 KB Output is correct
22 Correct 621 ms 79188 KB Output is correct
23 Correct 613 ms 79084 KB Output is correct
24 Correct 123 ms 73040 KB Output is correct
25 Correct 115 ms 73248 KB Output is correct
26 Correct 316 ms 78420 KB Output is correct
27 Correct 304 ms 78676 KB Output is correct
28 Correct 508 ms 77804 KB Output is correct
29 Correct 514 ms 77832 KB Output is correct
30 Correct 484 ms 77804 KB Output is correct
31 Correct 427 ms 77040 KB Output is correct
32 Correct 443 ms 77184 KB Output is correct
33 Correct 583 ms 77072 KB Output is correct
34 Correct 822 ms 78812 KB Output is correct
35 Correct 847 ms 78904 KB Output is correct
36 Correct 826 ms 78808 KB Output is correct
37 Correct 846 ms 78720 KB Output is correct
38 Correct 833 ms 78932 KB Output is correct
39 Correct 831 ms 78724 KB Output is correct
40 Correct 831 ms 78772 KB Output is correct
41 Correct 851 ms 78768 KB Output is correct
42 Correct 796 ms 78724 KB Output is correct
43 Correct 821 ms 78928 KB Output is correct
44 Correct 911 ms 78740 KB Output is correct
45 Correct 802 ms 78840 KB Output is correct
46 Correct 863 ms 78932 KB Output is correct
47 Correct 26 ms 78928 KB Output is correct
48 Correct 24 ms 78940 KB Output is correct
49 Correct 34 ms 78932 KB Output is correct
50 Correct 9 ms 70388 KB Output is correct
51 Correct 9 ms 70392 KB Output is correct
52 Correct 9 ms 70236 KB Output is correct
53 Execution timed out 2019 ms 104640 KB Time limit exceeded
54 Halted 0 ms 0 KB -