#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
#define ll long long
#define F first
#define S second
#define pii pair<int,int>
const int mod = 1e9 + 7;
const int mxN = 2e5 + 4;
using namespace std;
struct DNA{
int aT = 0,aC = 0,aA = 0,apT = 0,apC = 0,apA = 0;
int bT = 0,bC = 0,bA = 0,bpT = 0,bpC = 0,bpA = 0;
friend DNA operator+(DNA a, DNA b){
a.aT += b.aT;
a.aC += b.aC;
a.aA += b.aA;
a.apT += b.apT;
a.apC += b.apC;
a.apA += b.apA;
a.bT += b.bT;
a.bC += b.bC;
a.bA += b.bpA;
a.bpT += b.bpT;
a.bpC += b.bpC;
a.bpA += b.bpA;
return a;
}
friend DNA operator-(DNA a, DNA b){
a.aT -= b.aT;
a.aC -= b.aC;
a.aA -= b.aA;
a.apT -= b.apT;
a.apC -= b.apC;
a.apA -= b.apA;
a.bT -= b.bT;
a.bC -= b.bC;
a.bA -= b.bpA;
a.bpT -= b.bpT;
a.bpC -= b.bpC;
a.bpA -= b.bpA;
return a;
}
};
int getD(DNA og){
if(og.aA != og.bA || og.aC != og.bC || og.aT != og.bT) return -1;
int ans = 0;
int mn = min({og.apA,og.apT,og.bpA,og.bpT});
og.apA -= mn;
og.apT -= mn;
og.bpA -= mn;
og.bpT -= mn;
ans += mn;
mn = min({og.apA,og.apC,og.bpA,og.bpC});
og.apA -= mn;
og.apC -= mn;
og.bpA -= mn;
og.bpC -= mn;
ans += mn;
mn = min({og.apC,og.apT,og.bpC,og.bpT});
og.apC -= mn;
og.apT -= mn;
og.bpT -= mn;
og.bpC -= mn;
ans += mn;
return ans + max(og.apT + og.apA + og.apC,og.bpT + og.bpC + og.bpA);
}
DNA prfx[mxN];
void init(std::string a, std::string b) {
for(int i = 1;i <= a.size();i++){
prfx[i] = prfx[i] + prfx[i - 1];
if(a[i - 1] == 'A'){
if(a[i - 1] != b[i - 1]) prfx[i].apA++;
prfx[i].aA++;
}
if(a[i - 1] == 'T'){
if(a[i - 1] != b[i - 1]) prfx[i].apT++;
prfx[i].aT++;
}
if(a[i - 1] == 'C'){
if(a[i - 1] != b[i - 1]) prfx[i].apC++;
prfx[i].aC++;
}
if(b[i - 1] == 'A'){
if(b[i - 1] != a[i - 1]) prfx[i].bpA++;
prfx[i].bA++;
}
if(b[i - 1] == 'T'){
if(b[i - 1] != a[i - 1]) prfx[i].bpT++;
prfx[i].bT++;
}
if(b[i - 1] == 'C'){
if(b[i - 1] != a[i - 1]) prfx[i].bpC++;
prfx[i].bC++;
}
}
}
int get_distance(int x, int y) {
DNA s = prfx[y + 1] - prfx[x];
return getD(s);
}
// int main() {
// int n, q;
// assert(scanf("%d %d", &n, &q) == 2);
// char A[n+1], B[n+1];
// assert(scanf("%s", A) == 1);
// assert(scanf("%s", B) == 1);
// std::string a = std::string(A);
// std::string b = std::string(B);
// 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:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 1;i <= a.size();i++){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
7172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5740 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5740 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5740 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
7172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
