#include<bits/stdc++.h>
#include "dna.h"
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
#define MAXN 100005
int N;
int pre[3][MAXN];
int trans[3][3][MAXN];
inline int toint(char c){
return (c == 'A' ? 0 : (c == 'C' ? 1 : 2));
}
void init(string A, string B){
N = A.size();
F0R(a, 3){
F0R(b, 3){
F0R(i, N){
trans[a][b][i] = 0;
}
}
}
F0R(a, 3){
F0R(i, N){
pre[a][i] = 0;
}
}
F0R(i, N){
if(i){
F0R(a, 3){
pre[a][i] = pre[a][i - 1];
F0R(b, 3){
trans[a][b][i] = trans[a][b][i - 1];
}
}
}
++pre[toint(A[i])][i];
--pre[toint(B[i])][i];
++trans[toint(A[i])][toint(B[i])][i];
}
}
inline bool ok(int x, int y){
if(x){
return pre[0][y] == pre[0][x - 1] && pre[1][y] == pre[1][x - 1] && pre[2][y] == pre[2][x - 1];
}else{
return pre[0][y] == 0 && pre[1][y] == 0 && pre[2][y] == 0;
}
}
int get_distance(int x, int y){
if(!ok(x, y)){
return -1;
}
int res[3][3];
F0R(a, 3){
F0R(b, 3){
res[a][b] = trans[a][b][y];
if(x){
res[a][b] -= trans[a][b][x - 1];
}
// cerr << "res[" << a << "][" << b << "] = " << res[a][b] << '\n';
}
}
int cnt[3];
cnt[0] = min(res[0][1], res[1][0]);
res[0][1] -= cnt[0];
res[1][0] -= cnt[0];
cnt[1] = min(res[2][1], res[1][2]);
res[2][1] -= cnt[1];
res[1][2] -= cnt[1];
cnt[2] = min(res[0][2], res[2][0]);
res[0][2] -= cnt[2];
res[2][0] -= cnt[2];
// F0R(a, 3){
// cerr << "cnt[" << a << "] = " << cnt[a] << '\n';
// }
return cnt[0] + cnt[1] + cnt[2] + ((res[0][1] + res[1][0]) << 1);
}
/*
signed main(){
string A, B;
int Q;
cin >> A >> B >> Q;
init(A, B);
while(Q--){
int x, y;
cin >> x >> y;
cout << get_distance(x, y) << '\n';
}
return 0;
}
*/
/*
ACTATA
ATACAT
3
1 3
3 5
4 5
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
8204 KB |
Output is correct |
2 |
Correct |
34 ms |
8184 KB |
Output is correct |
3 |
Correct |
38 ms |
7776 KB |
Output is correct |
4 |
Correct |
39 ms |
8156 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
6 ms |
5748 KB |
Output is correct |
5 |
Correct |
6 ms |
5696 KB |
Output is correct |
6 |
Correct |
6 ms |
5804 KB |
Output is correct |
7 |
Correct |
5 ms |
5332 KB |
Output is correct |
8 |
Correct |
6 ms |
5716 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
6 ms |
5748 KB |
Output is correct |
5 |
Correct |
6 ms |
5696 KB |
Output is correct |
6 |
Correct |
6 ms |
5804 KB |
Output is correct |
7 |
Correct |
5 ms |
5332 KB |
Output is correct |
8 |
Correct |
6 ms |
5716 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
10 |
Correct |
39 ms |
8220 KB |
Output is correct |
11 |
Correct |
41 ms |
8188 KB |
Output is correct |
12 |
Correct |
35 ms |
8216 KB |
Output is correct |
13 |
Correct |
35 ms |
8308 KB |
Output is correct |
14 |
Correct |
35 ms |
8556 KB |
Output is correct |
15 |
Correct |
37 ms |
8468 KB |
Output is correct |
16 |
Correct |
41 ms |
8036 KB |
Output is correct |
17 |
Correct |
47 ms |
8212 KB |
Output is correct |
18 |
Correct |
38 ms |
8456 KB |
Output is correct |
19 |
Correct |
31 ms |
8168 KB |
Output is correct |
20 |
Correct |
32 ms |
8300 KB |
Output is correct |
21 |
Correct |
33 ms |
8520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
6 ms |
5748 KB |
Output is correct |
5 |
Correct |
6 ms |
5696 KB |
Output is correct |
6 |
Correct |
6 ms |
5804 KB |
Output is correct |
7 |
Correct |
5 ms |
5332 KB |
Output is correct |
8 |
Correct |
6 ms |
5716 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
10 |
Correct |
5 ms |
5336 KB |
Output is correct |
11 |
Correct |
7 ms |
5716 KB |
Output is correct |
12 |
Correct |
6 ms |
5460 KB |
Output is correct |
13 |
Correct |
6 ms |
5776 KB |
Output is correct |
14 |
Correct |
8 ms |
5716 KB |
Output is correct |
15 |
Correct |
5 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
8204 KB |
Output is correct |
2 |
Correct |
34 ms |
8184 KB |
Output is correct |
3 |
Correct |
38 ms |
7776 KB |
Output is correct |
4 |
Correct |
39 ms |
8156 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
308 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
304 KB |
Output is correct |
11 |
Correct |
6 ms |
5748 KB |
Output is correct |
12 |
Correct |
6 ms |
5696 KB |
Output is correct |
13 |
Correct |
6 ms |
5804 KB |
Output is correct |
14 |
Correct |
5 ms |
5332 KB |
Output is correct |
15 |
Correct |
6 ms |
5716 KB |
Output is correct |
16 |
Correct |
5 ms |
5716 KB |
Output is correct |
17 |
Correct |
39 ms |
8220 KB |
Output is correct |
18 |
Correct |
41 ms |
8188 KB |
Output is correct |
19 |
Correct |
35 ms |
8216 KB |
Output is correct |
20 |
Correct |
35 ms |
8308 KB |
Output is correct |
21 |
Correct |
35 ms |
8556 KB |
Output is correct |
22 |
Correct |
37 ms |
8468 KB |
Output is correct |
23 |
Correct |
41 ms |
8036 KB |
Output is correct |
24 |
Correct |
47 ms |
8212 KB |
Output is correct |
25 |
Correct |
38 ms |
8456 KB |
Output is correct |
26 |
Correct |
31 ms |
8168 KB |
Output is correct |
27 |
Correct |
32 ms |
8300 KB |
Output is correct |
28 |
Correct |
33 ms |
8520 KB |
Output is correct |
29 |
Correct |
5 ms |
5336 KB |
Output is correct |
30 |
Correct |
7 ms |
5716 KB |
Output is correct |
31 |
Correct |
6 ms |
5460 KB |
Output is correct |
32 |
Correct |
6 ms |
5776 KB |
Output is correct |
33 |
Correct |
8 ms |
5716 KB |
Output is correct |
34 |
Correct |
5 ms |
5716 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
33 ms |
7772 KB |
Output is correct |
37 |
Correct |
34 ms |
8128 KB |
Output is correct |
38 |
Correct |
37 ms |
8300 KB |
Output is correct |
39 |
Correct |
42 ms |
8568 KB |
Output is correct |
40 |
Correct |
37 ms |
8584 KB |
Output is correct |
41 |
Correct |
5 ms |
5732 KB |
Output is correct |
42 |
Correct |
34 ms |
8204 KB |
Output is correct |
43 |
Correct |
33 ms |
8404 KB |
Output is correct |
44 |
Correct |
45 ms |
8448 KB |
Output is correct |
45 |
Correct |
34 ms |
8172 KB |
Output is correct |
46 |
Correct |
34 ms |
8440 KB |
Output is correct |
47 |
Correct |
33 ms |
8436 KB |
Output is correct |