#include <bits/stdc++.h>
#define nl '\n'
#define pb push_back
#define ll long long
#define VMAX 100001
#define NMAX 35005
#define INF 10000000000000000
using namespace std;
string A,B;
int n,p=0;
int cod[256];
int prefixsum[4][4][100005],aux[4][4];
void init(string a,string b)
{
A=a;
B=b;
n=a.size();
cod['A']=1;
cod['C']=2;
cod['T']=3;
for(int k1=1;k1<=3;k1++)
{
for(int k2=1;k2<=3;k2++)
{
for(int i=0;i<n;i++)
{
if(i==0)
{
prefixsum[k1][k2][i]=0;
}
else
{
prefixsum[k1][k2][i]=prefixsum[k1][k2][i-1];
}
if(cod[A[i]]==k1&&cod[B[i]]==k2)
{
prefixsum[k1][k2][i]++;
}
}
}
}
}
int get_distance(int x,int y)
{
int ans=y-x+1,cycles=0;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
aux[i][j]=prefixsum[i][j][y];
if(x)
{
aux[i][j]-=prefixsum[i][j][x-1];
}
}
}
for(int i=1;i<=3;i++)
{
cycles+=aux[i][i];
aux[i][i]=0;
}
for(int i=1;i<=3;i++)
{
for(int j=i+1;j<=3;j++)
{
int p=min(aux[i][j],aux[j][i]);
aux[i][j]-=p;
aux[j][i]-=p;
cycles+=p;
}
}
///mai avem doar cycluri de lungime 3
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
for(int k=1;k<=3;k++)
{
if(i!=j&&i!=k&&j!=k)
{
int p=min(min(aux[i][j],aux[j][k]),aux[k][i]);
cycles+=p;
aux[i][j]-=p;
aux[j][k]-=p;
aux[k][i]-=p;
p=min(min(aux[i][k],aux[j][i]),aux[k][j]);
aux[i][k]-=p;
aux[j][i]-=p;
aux[k][j]-=p;
cycles+=p;
}
}
}
}
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
if(aux[i][j]) return -1;
}
}
return ans-cycles;
}
/*
int main()
{
int N, q;
assert(scanf("%d %d", &N, &q) == 2);
char X[n+1], Y[n+1];
assert(scanf("%s", X) == 1);
assert(scanf("%s", Y) == 1);
std::string a = std::string(X);
std::string b = std::string(Y);
std::vector<int> x(q), y(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d %d", &x[i], &y[i]) == 2);
}
fclose(stdin);
std::vector<int> results(q);
init(a, b);
for (int i = 0; i < q; i++) {
results[i] = get_distance(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", results[i]);
}
fclose(stdout);
return 0;
}
*/
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:36:28: warning: array subscript has type 'char' [-Wchar-subscripts]
36 | if(cod[A[i]]==k1&&cod[B[i]]==k2)
| ^
dna.cpp:36:43: warning: array subscript has type 'char' [-Wchar-subscripts]
36 | if(cod[A[i]]==k1&&cod[B[i]]==k2)
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
5928 KB |
Output is correct |
2 |
Correct |
56 ms |
5912 KB |
Output is correct |
3 |
Correct |
54 ms |
5528 KB |
Output is correct |
4 |
Correct |
57 ms |
5956 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
10 ms |
4476 KB |
Output is correct |
5 |
Correct |
10 ms |
4556 KB |
Output is correct |
6 |
Correct |
11 ms |
4556 KB |
Output is correct |
7 |
Correct |
10 ms |
4248 KB |
Output is correct |
8 |
Correct |
11 ms |
4516 KB |
Output is correct |
9 |
Correct |
8 ms |
4556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
10 ms |
4476 KB |
Output is correct |
5 |
Correct |
10 ms |
4556 KB |
Output is correct |
6 |
Correct |
11 ms |
4556 KB |
Output is correct |
7 |
Correct |
10 ms |
4248 KB |
Output is correct |
8 |
Correct |
11 ms |
4516 KB |
Output is correct |
9 |
Correct |
8 ms |
4556 KB |
Output is correct |
10 |
Correct |
74 ms |
5888 KB |
Output is correct |
11 |
Correct |
56 ms |
5924 KB |
Output is correct |
12 |
Correct |
55 ms |
5956 KB |
Output is correct |
13 |
Correct |
56 ms |
6068 KB |
Output is correct |
14 |
Correct |
59 ms |
6336 KB |
Output is correct |
15 |
Correct |
55 ms |
6212 KB |
Output is correct |
16 |
Correct |
54 ms |
5956 KB |
Output is correct |
17 |
Correct |
55 ms |
6092 KB |
Output is correct |
18 |
Correct |
53 ms |
6308 KB |
Output is correct |
19 |
Correct |
58 ms |
6020 KB |
Output is correct |
20 |
Correct |
52 ms |
6212 KB |
Output is correct |
21 |
Correct |
57 ms |
6328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
10 ms |
4476 KB |
Output is correct |
5 |
Correct |
10 ms |
4556 KB |
Output is correct |
6 |
Correct |
11 ms |
4556 KB |
Output is correct |
7 |
Correct |
10 ms |
4248 KB |
Output is correct |
8 |
Correct |
11 ms |
4516 KB |
Output is correct |
9 |
Correct |
8 ms |
4556 KB |
Output is correct |
10 |
Correct |
10 ms |
4268 KB |
Output is correct |
11 |
Correct |
11 ms |
4512 KB |
Output is correct |
12 |
Correct |
11 ms |
4328 KB |
Output is correct |
13 |
Correct |
11 ms |
4596 KB |
Output is correct |
14 |
Correct |
12 ms |
4556 KB |
Output is correct |
15 |
Correct |
8 ms |
4556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
5928 KB |
Output is correct |
2 |
Correct |
56 ms |
5912 KB |
Output is correct |
3 |
Correct |
54 ms |
5528 KB |
Output is correct |
4 |
Correct |
57 ms |
5956 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
10 ms |
4476 KB |
Output is correct |
12 |
Correct |
10 ms |
4556 KB |
Output is correct |
13 |
Correct |
11 ms |
4556 KB |
Output is correct |
14 |
Correct |
10 ms |
4248 KB |
Output is correct |
15 |
Correct |
11 ms |
4516 KB |
Output is correct |
16 |
Correct |
8 ms |
4556 KB |
Output is correct |
17 |
Correct |
74 ms |
5888 KB |
Output is correct |
18 |
Correct |
56 ms |
5924 KB |
Output is correct |
19 |
Correct |
55 ms |
5956 KB |
Output is correct |
20 |
Correct |
56 ms |
6068 KB |
Output is correct |
21 |
Correct |
59 ms |
6336 KB |
Output is correct |
22 |
Correct |
55 ms |
6212 KB |
Output is correct |
23 |
Correct |
54 ms |
5956 KB |
Output is correct |
24 |
Correct |
55 ms |
6092 KB |
Output is correct |
25 |
Correct |
53 ms |
6308 KB |
Output is correct |
26 |
Correct |
58 ms |
6020 KB |
Output is correct |
27 |
Correct |
52 ms |
6212 KB |
Output is correct |
28 |
Correct |
57 ms |
6328 KB |
Output is correct |
29 |
Correct |
10 ms |
4268 KB |
Output is correct |
30 |
Correct |
11 ms |
4512 KB |
Output is correct |
31 |
Correct |
11 ms |
4328 KB |
Output is correct |
32 |
Correct |
11 ms |
4596 KB |
Output is correct |
33 |
Correct |
12 ms |
4556 KB |
Output is correct |
34 |
Correct |
8 ms |
4556 KB |
Output is correct |
35 |
Correct |
1 ms |
316 KB |
Output is correct |
36 |
Correct |
55 ms |
5520 KB |
Output is correct |
37 |
Correct |
57 ms |
5956 KB |
Output is correct |
38 |
Correct |
58 ms |
6084 KB |
Output is correct |
39 |
Correct |
57 ms |
6272 KB |
Output is correct |
40 |
Correct |
58 ms |
6336 KB |
Output is correct |
41 |
Correct |
6 ms |
4556 KB |
Output is correct |
42 |
Correct |
54 ms |
6084 KB |
Output is correct |
43 |
Correct |
60 ms |
6324 KB |
Output is correct |
44 |
Correct |
54 ms |
6340 KB |
Output is correct |
45 |
Correct |
50 ms |
6184 KB |
Output is correct |
46 |
Correct |
52 ms |
6344 KB |
Output is correct |
47 |
Correct |
51 ms |
6340 KB |
Output is correct |