Submission #937906

#	Time	Username	Problem	Language	Result	Execution time	Memory
937906		emad234	Mutating DNA (IOI21_dna)	C++17	56 / 100	35 ms	7444 KiB

dna

#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.apA;
		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.apA;
		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 (stderr)

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++){
      |                ~~^~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16