# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
454588 | 2021-08-05T06:12:46 Z | ogibogi2004 | Mutating DNA (IOI21_dna) | C++17 | 83 ms | 11052 KB |
#include "dna.h" #include <bits/stdc++.h> using namespace std; const int MAXN=1e5+6; int prcnt[MAXN][4][4]; int prcnt1[MAXN][4]; void init(string a, string b) { for(int i=1;i<=a.size();i++) { for(int j1=0;j1<4;j1++) { for(int j2=0;j2<4;j2++) { prcnt[i][j1][j2]=prcnt[i-1][j1][j2]; } prcnt1[i][j1]=prcnt1[i-1][j1]; } int c1=0,c2=0; if(a[i-1]=='A')c1=1; if(a[i-1]=='C')c1=2; if(a[i-1]=='T')c1=3; if(b[i-1]=='A')c2=1; if(b[i-1]=='C')c2=2; if(b[i-1]=='T')c2=3; prcnt[i][c1][c2]++; prcnt1[i][c1]++; prcnt1[i][c2]--; } } int get_distance(int x, int y) { x++;y++; int cnt[4][4]; for(int j1=0;j1<4;j1++) { for(int j2=0;j2<4;j2++) { cnt[j1][j2]=prcnt[y][j1][j2]-prcnt[x-1][j1][j2]; } } //cout<<"*\n"; int cntswaps=0; for(int j=0;j<4;j++) { if(prcnt1[y][j]-prcnt1[x-1][j]!=0)return -1; } for(int j1=0;j1<4;j1++) { for(int j2=0;j2<4;j2++) { if(j1==j2)continue; cntswaps+=cnt[j1][j2]; } } for(int j1=1;j1<4;j1++) { for(int j2=j1+1;j2<4;j2++) { int t=min(cnt[j1][j2],cnt[j2][j1]); cnt[j1][j2]-=t;cnt[j2][j1]-=t; cntswaps-=t; } } int cnt1=0; set<int>s; for(int j1=1;j1<4;j1++) { for(int j2=1;j2<4;j2++) { if(j1==j2)continue; if(cnt[j1][j2]>0) { s.insert(cnt[j1][j2]); cnt1++; } } } if(cnt1==0)return cntswaps; //cout<<s.size()<<endl; if(s.size()!=1)assert(false); return cntswaps-(*s.begin()); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 9860 KB | Output is correct |
2 | Correct | 61 ms | 10632 KB | Output is correct |
3 | Correct | 52 ms | 9852 KB | Output is correct |
4 | Correct | 58 ms | 10524 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 300 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 7 ms | 8780 KB | Output is correct |
5 | Correct | 8 ms | 8884 KB | Output is correct |
6 | Correct | 7 ms | 8780 KB | Output is correct |
7 | Correct | 8 ms | 8268 KB | Output is correct |
8 | Correct | 7 ms | 8840 KB | Output is correct |
9 | Correct | 7 ms | 8908 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 7 ms | 8780 KB | Output is correct |
5 | Correct | 8 ms | 8884 KB | Output is correct |
6 | Correct | 7 ms | 8780 KB | Output is correct |
7 | Correct | 8 ms | 8268 KB | Output is correct |
8 | Correct | 7 ms | 8840 KB | Output is correct |
9 | Correct | 7 ms | 8908 KB | Output is correct |
10 | Correct | 61 ms | 10500 KB | Output is correct |
11 | Correct | 64 ms | 10568 KB | Output is correct |
12 | Correct | 71 ms | 10392 KB | Output is correct |
13 | Correct | 68 ms | 10608 KB | Output is correct |
14 | Correct | 76 ms | 10928 KB | Output is correct |
15 | Correct | 58 ms | 10848 KB | Output is correct |
16 | Correct | 49 ms | 10380 KB | Output is correct |
17 | Correct | 60 ms | 10624 KB | Output is correct |
18 | Correct | 63 ms | 11008 KB | Output is correct |
19 | Correct | 45 ms | 10384 KB | Output is correct |
20 | Correct | 52 ms | 10600 KB | Output is correct |
21 | Correct | 45 ms | 10944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 7 ms | 8780 KB | Output is correct |
5 | Correct | 8 ms | 8884 KB | Output is correct |
6 | Correct | 7 ms | 8780 KB | Output is correct |
7 | Correct | 8 ms | 8268 KB | Output is correct |
8 | Correct | 7 ms | 8840 KB | Output is correct |
9 | Correct | 7 ms | 8908 KB | Output is correct |
10 | Correct | 7 ms | 8080 KB | Output is correct |
11 | Correct | 9 ms | 8888 KB | Output is correct |
12 | Correct | 9 ms | 8248 KB | Output is correct |
13 | Correct | 8 ms | 8852 KB | Output is correct |
14 | Correct | 9 ms | 8816 KB | Output is correct |
15 | Correct | 7 ms | 8836 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 9860 KB | Output is correct |
2 | Correct | 61 ms | 10632 KB | Output is correct |
3 | Correct | 52 ms | 9852 KB | Output is correct |
4 | Correct | 58 ms | 10524 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 300 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
11 | Correct | 7 ms | 8780 KB | Output is correct |
12 | Correct | 8 ms | 8884 KB | Output is correct |
13 | Correct | 7 ms | 8780 KB | Output is correct |
14 | Correct | 8 ms | 8268 KB | Output is correct |
15 | Correct | 7 ms | 8840 KB | Output is correct |
16 | Correct | 7 ms | 8908 KB | Output is correct |
17 | Correct | 61 ms | 10500 KB | Output is correct |
18 | Correct | 64 ms | 10568 KB | Output is correct |
19 | Correct | 71 ms | 10392 KB | Output is correct |
20 | Correct | 68 ms | 10608 KB | Output is correct |
21 | Correct | 76 ms | 10928 KB | Output is correct |
22 | Correct | 58 ms | 10848 KB | Output is correct |
23 | Correct | 49 ms | 10380 KB | Output is correct |
24 | Correct | 60 ms | 10624 KB | Output is correct |
25 | Correct | 63 ms | 11008 KB | Output is correct |
26 | Correct | 45 ms | 10384 KB | Output is correct |
27 | Correct | 52 ms | 10600 KB | Output is correct |
28 | Correct | 45 ms | 10944 KB | Output is correct |
29 | Correct | 7 ms | 8080 KB | Output is correct |
30 | Correct | 9 ms | 8888 KB | Output is correct |
31 | Correct | 9 ms | 8248 KB | Output is correct |
32 | Correct | 8 ms | 8852 KB | Output is correct |
33 | Correct | 9 ms | 8816 KB | Output is correct |
34 | Correct | 7 ms | 8836 KB | Output is correct |
35 | Correct | 1 ms | 204 KB | Output is correct |
36 | Correct | 50 ms | 9920 KB | Output is correct |
37 | Correct | 63 ms | 10616 KB | Output is correct |
38 | Correct | 66 ms | 10468 KB | Output is correct |
39 | Correct | 83 ms | 11004 KB | Output is correct |
40 | Correct | 66 ms | 10996 KB | Output is correct |
41 | Correct | 7 ms | 8888 KB | Output is correct |
42 | Correct | 72 ms | 10472 KB | Output is correct |
43 | Correct | 54 ms | 10944 KB | Output is correct |
44 | Correct | 55 ms | 10960 KB | Output is correct |
45 | Correct | 49 ms | 10520 KB | Output is correct |
46 | Correct | 51 ms | 11052 KB | Output is correct |
47 | Correct | 56 ms | 10980 KB | Output is correct |