#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=101000;
const char c[3]={'A','T','C'};
int pref[N][3][3],cnt[3][3];
void init(string a,string b) {
int n=SZ(a);
rep(i,0,n) rep(p,0,3) rep(q,0,3) pref[i][p][q]=pref[i-1][p][q]+(a[i]==c[p]&&b[i]==c[q]);
}
int get_distance(int l,int r) {
VI sx(3),sy(3);
rep(i,0,3) rep(j,0,3) {
int occ=pref[r][i][j]-(l>0?pref[l-1][i][j]:0);
cnt[i][j]=occ; sx[i]+=occ; sy[j]+=occ;
}
rep(i,0,3) if (sx[i]!=sy[i]) return -1;
int ans=0;
rep(i,0,3) rep(j,i+1,3) {
int ft=min(cnt[i][j],cnt[j][i]);
ans+=ft; cnt[i][j]-=ft; cnt[j][i]-=ft;
}
int ost=0;
rep(i,0,3) rep(j,0,3) if (i!=j) ost+=cnt[i][j];
return ans+ost*2/3;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
5636 KB |
Output is correct |
2 |
Correct |
32 ms |
7024 KB |
Output is correct |
3 |
Correct |
33 ms |
6676 KB |
Output is correct |
4 |
Correct |
35 ms |
7036 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
4 ms |
4540 KB |
Output is correct |
5 |
Correct |
4 ms |
4532 KB |
Output is correct |
6 |
Correct |
4 ms |
4556 KB |
Output is correct |
7 |
Correct |
4 ms |
4300 KB |
Output is correct |
8 |
Correct |
4 ms |
4556 KB |
Output is correct |
9 |
Correct |
4 ms |
4556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
4 ms |
4540 KB |
Output is correct |
5 |
Correct |
4 ms |
4532 KB |
Output is correct |
6 |
Correct |
4 ms |
4556 KB |
Output is correct |
7 |
Correct |
4 ms |
4300 KB |
Output is correct |
8 |
Correct |
4 ms |
4556 KB |
Output is correct |
9 |
Correct |
4 ms |
4556 KB |
Output is correct |
10 |
Correct |
35 ms |
6916 KB |
Output is correct |
11 |
Correct |
34 ms |
7056 KB |
Output is correct |
12 |
Correct |
35 ms |
7012 KB |
Output is correct |
13 |
Correct |
37 ms |
7188 KB |
Output is correct |
14 |
Correct |
37 ms |
7368 KB |
Output is correct |
15 |
Correct |
35 ms |
7296 KB |
Output is correct |
16 |
Correct |
32 ms |
6920 KB |
Output is correct |
17 |
Correct |
32 ms |
7052 KB |
Output is correct |
18 |
Correct |
32 ms |
7296 KB |
Output is correct |
19 |
Correct |
31 ms |
6972 KB |
Output is correct |
20 |
Correct |
31 ms |
7052 KB |
Output is correct |
21 |
Correct |
31 ms |
7288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
4 ms |
4540 KB |
Output is correct |
5 |
Correct |
4 ms |
4532 KB |
Output is correct |
6 |
Correct |
4 ms |
4556 KB |
Output is correct |
7 |
Correct |
4 ms |
4300 KB |
Output is correct |
8 |
Correct |
4 ms |
4556 KB |
Output is correct |
9 |
Correct |
4 ms |
4556 KB |
Output is correct |
10 |
Correct |
4 ms |
4172 KB |
Output is correct |
11 |
Correct |
4 ms |
4556 KB |
Output is correct |
12 |
Correct |
4 ms |
4300 KB |
Output is correct |
13 |
Correct |
4 ms |
4556 KB |
Output is correct |
14 |
Correct |
4 ms |
4556 KB |
Output is correct |
15 |
Correct |
4 ms |
4556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
5636 KB |
Output is correct |
2 |
Correct |
32 ms |
7024 KB |
Output is correct |
3 |
Correct |
33 ms |
6676 KB |
Output is correct |
4 |
Correct |
35 ms |
7036 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
4 ms |
4540 KB |
Output is correct |
12 |
Correct |
4 ms |
4532 KB |
Output is correct |
13 |
Correct |
4 ms |
4556 KB |
Output is correct |
14 |
Correct |
4 ms |
4300 KB |
Output is correct |
15 |
Correct |
4 ms |
4556 KB |
Output is correct |
16 |
Correct |
4 ms |
4556 KB |
Output is correct |
17 |
Correct |
35 ms |
6916 KB |
Output is correct |
18 |
Correct |
34 ms |
7056 KB |
Output is correct |
19 |
Correct |
35 ms |
7012 KB |
Output is correct |
20 |
Correct |
37 ms |
7188 KB |
Output is correct |
21 |
Correct |
37 ms |
7368 KB |
Output is correct |
22 |
Correct |
35 ms |
7296 KB |
Output is correct |
23 |
Correct |
32 ms |
6920 KB |
Output is correct |
24 |
Correct |
32 ms |
7052 KB |
Output is correct |
25 |
Correct |
32 ms |
7296 KB |
Output is correct |
26 |
Correct |
31 ms |
6972 KB |
Output is correct |
27 |
Correct |
31 ms |
7052 KB |
Output is correct |
28 |
Correct |
31 ms |
7288 KB |
Output is correct |
29 |
Correct |
4 ms |
4172 KB |
Output is correct |
30 |
Correct |
4 ms |
4556 KB |
Output is correct |
31 |
Correct |
4 ms |
4300 KB |
Output is correct |
32 |
Correct |
4 ms |
4556 KB |
Output is correct |
33 |
Correct |
4 ms |
4556 KB |
Output is correct |
34 |
Correct |
4 ms |
4556 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
35 ms |
6672 KB |
Output is correct |
37 |
Correct |
34 ms |
7032 KB |
Output is correct |
38 |
Correct |
34 ms |
7144 KB |
Output is correct |
39 |
Correct |
37 ms |
7296 KB |
Output is correct |
40 |
Correct |
37 ms |
7296 KB |
Output is correct |
41 |
Correct |
4 ms |
4556 KB |
Output is correct |
42 |
Correct |
32 ms |
7004 KB |
Output is correct |
43 |
Correct |
34 ms |
7292 KB |
Output is correct |
44 |
Correct |
34 ms |
7284 KB |
Output is correct |
45 |
Correct |
31 ms |
7056 KB |
Output is correct |
46 |
Correct |
31 ms |
7328 KB |
Output is correct |
47 |
Correct |
32 ms |
7276 KB |
Output is correct |