#include "dna.h"
#include <bits/stdc++.h>
#define ll long long
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 100005
ll n;
ll ps[maxn][4][4];
ll p[maxn][4];
map<char,ll> mp;
void init(std::string a, std::string b) {
mp['A'] = 1;
mp['T'] = 2;
mp['C'] = 3;
n = a.size();
for(ll i = 1;i<=n;i++){
ll ca = mp[a[i-1]];
ll cb = mp[b[i-1]];
for(ll j = 1;j<=3;j++){
p[i][j] = p[i-1][j];
for(ll k = 1;k<=3;k++){
ps[i][j][k] = ps[i-1][j][k];
}
}
p[i][ca]++;
p[i][cb]++;
ps[i][ca][cb]++;
}
}
ll f[4][4];
ll c[4];
ll cnt[4];
int get_distance(int x, int y) {
x++; y++;
for(ll i = 1;i<=3;i++) for(ll j = 1;j<=3;j++) f[i][j] = ps[y][i][j] - ps[x-1][i][j];
for(ll i = 1;i<=3;i++) c[i] = 0;
for(ll i = 1;i<=3;i++) cnt[i] = p[y][i] - p[x-1][i];
ll ans = 0;
set<ll> s;
for(ll i = 1;i<=3;i++){
for(ll j = i+1;j<=3;j++){
ll x = min(f[i][j],f[j][i]);
ans+=x;
f[i][j]-=x;
f[j][i]-=x;
if(f[i][j]){
c[i]++;
s.insert(f[i][j]);
}
else if(f[j][i]){
c[j]++;
s.insert(f[j][i]);
}
}
}
ll sum = c[1] + c[2] + c[3];
if(sum){
for(ll i = 1;i<=3;i++){
if(c[i]!=1&&(cnt[i]!=0)) return -1;
}
}
if(s.size()>1) return -1;
if(s.size()) ans+=2*(*s.begin());
return ans;
}
/**
6 3
ATACAT ACTATA
1 3
4 5
3 5
5 3
ATATTA AATATT
1 4
1 2
1 6
**/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
17548 KB |
Output is correct |
2 |
Correct |
49 ms |
17772 KB |
Output is correct |
3 |
Correct |
48 ms |
16364 KB |
Output is correct |
4 |
Correct |
50 ms |
18928 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
11 ms |
16336 KB |
Output is correct |
5 |
Correct |
11 ms |
16420 KB |
Output is correct |
6 |
Correct |
10 ms |
16312 KB |
Output is correct |
7 |
Correct |
10 ms |
15388 KB |
Output is correct |
8 |
Correct |
12 ms |
16468 KB |
Output is correct |
9 |
Correct |
9 ms |
16468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
11 ms |
16336 KB |
Output is correct |
5 |
Correct |
11 ms |
16420 KB |
Output is correct |
6 |
Correct |
10 ms |
16312 KB |
Output is correct |
7 |
Correct |
10 ms |
15388 KB |
Output is correct |
8 |
Correct |
12 ms |
16468 KB |
Output is correct |
9 |
Correct |
9 ms |
16468 KB |
Output is correct |
10 |
Correct |
49 ms |
17676 KB |
Output is correct |
11 |
Correct |
50 ms |
17808 KB |
Output is correct |
12 |
Correct |
48 ms |
17064 KB |
Output is correct |
13 |
Correct |
48 ms |
17440 KB |
Output is correct |
14 |
Correct |
49 ms |
18148 KB |
Output is correct |
15 |
Correct |
49 ms |
18056 KB |
Output is correct |
16 |
Correct |
43 ms |
17076 KB |
Output is correct |
17 |
Correct |
44 ms |
17384 KB |
Output is correct |
18 |
Correct |
46 ms |
18172 KB |
Output is correct |
19 |
Correct |
37 ms |
17048 KB |
Output is correct |
20 |
Correct |
44 ms |
17528 KB |
Output is correct |
21 |
Correct |
37 ms |
18132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
11 ms |
16336 KB |
Output is correct |
5 |
Correct |
11 ms |
16420 KB |
Output is correct |
6 |
Correct |
10 ms |
16312 KB |
Output is correct |
7 |
Correct |
10 ms |
15388 KB |
Output is correct |
8 |
Correct |
12 ms |
16468 KB |
Output is correct |
9 |
Correct |
9 ms |
16468 KB |
Output is correct |
10 |
Correct |
9 ms |
15060 KB |
Output is correct |
11 |
Correct |
10 ms |
16724 KB |
Output is correct |
12 |
Correct |
10 ms |
15572 KB |
Output is correct |
13 |
Correct |
10 ms |
16612 KB |
Output is correct |
14 |
Correct |
10 ms |
16724 KB |
Output is correct |
15 |
Correct |
10 ms |
16704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
17548 KB |
Output is correct |
2 |
Correct |
49 ms |
17772 KB |
Output is correct |
3 |
Correct |
48 ms |
16364 KB |
Output is correct |
4 |
Correct |
50 ms |
18928 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
11 ms |
16336 KB |
Output is correct |
12 |
Correct |
11 ms |
16420 KB |
Output is correct |
13 |
Correct |
10 ms |
16312 KB |
Output is correct |
14 |
Correct |
10 ms |
15388 KB |
Output is correct |
15 |
Correct |
12 ms |
16468 KB |
Output is correct |
16 |
Correct |
9 ms |
16468 KB |
Output is correct |
17 |
Correct |
49 ms |
17676 KB |
Output is correct |
18 |
Correct |
50 ms |
17808 KB |
Output is correct |
19 |
Correct |
48 ms |
17064 KB |
Output is correct |
20 |
Correct |
48 ms |
17440 KB |
Output is correct |
21 |
Correct |
49 ms |
18148 KB |
Output is correct |
22 |
Correct |
49 ms |
18056 KB |
Output is correct |
23 |
Correct |
43 ms |
17076 KB |
Output is correct |
24 |
Correct |
44 ms |
17384 KB |
Output is correct |
25 |
Correct |
46 ms |
18172 KB |
Output is correct |
26 |
Correct |
37 ms |
17048 KB |
Output is correct |
27 |
Correct |
44 ms |
17528 KB |
Output is correct |
28 |
Correct |
37 ms |
18132 KB |
Output is correct |
29 |
Correct |
9 ms |
15060 KB |
Output is correct |
30 |
Correct |
10 ms |
16724 KB |
Output is correct |
31 |
Correct |
10 ms |
15572 KB |
Output is correct |
32 |
Correct |
10 ms |
16612 KB |
Output is correct |
33 |
Correct |
10 ms |
16724 KB |
Output is correct |
34 |
Correct |
10 ms |
16704 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
50 ms |
17696 KB |
Output is correct |
37 |
Correct |
49 ms |
19184 KB |
Output is correct |
38 |
Correct |
57 ms |
18476 KB |
Output is correct |
39 |
Correct |
58 ms |
19464 KB |
Output is correct |
40 |
Correct |
56 ms |
19512 KB |
Output is correct |
41 |
Correct |
9 ms |
16724 KB |
Output is correct |
42 |
Correct |
52 ms |
18552 KB |
Output is correct |
43 |
Correct |
55 ms |
19464 KB |
Output is correct |
44 |
Correct |
55 ms |
19416 KB |
Output is correct |
45 |
Correct |
42 ms |
18456 KB |
Output is correct |
46 |
Correct |
45 ms |
19452 KB |
Output is correct |
47 |
Correct |
44 ms |
19464 KB |
Output is correct |