Submission #1215649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215649		sangeraf	Mutating DNA (IOI21_dna)	C++20	100 / 100	24 ms	9228 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

string a, b;

void my_init(std::string aa, std::string bb) {
	a = aa;
	b = bb;
}

int my_get_distance(int x, int y) {
	int db1=0, db2=0;
	for(int i=x; i<=y; i++){
		if(a[i] == 'A' && b[i] == 'T') db1++;
		else if(a[i] == 'T' && b[i] == 'A') db2++;
	}
	if(db1 != db2) return -1;
	return db1;
}

const int maxn = 1e5 + 5;
int p1[maxn][3];
int p2[maxn][3];
int p3[maxn][3][3];
int s1[maxn];
int s2[maxn];

void init(string a, string b) {
    memset(p1, 0, sizeof(p1));
    memset(p2, 0, sizeof(p2));
    memset(p3, 0, sizeof(p3));
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == 'A')
            s1[i] = 0;
        else if (a[i] == 'C')
            s1[i] = 1;
        else
            s1[i] = 2;

        if (b[i] == 'A')
            s2[i] = 0;
        else if (b[i] == 'C')
            s2[i] = 1;
        else
            s2[i] = 2;
    }

    p1[0][s1[0]]++;
    p2[0][s2[0]]++;
    p3[0][s1[0]][s2[0]]++;
    for (int i = 1; i < a.size(); i++) {
        for (int t1 = 0; t1 <= 2; t1++) {
            for (int t2 = 0; t2 <= 2; t2++) {
                p3[i][t1][t2] = p3[i - 1][t1][t2];
            }
            p1[i][t1] = p1[i - 1][t1];
            p2[i][t1] = p2[i - 1][t1];
        }

        p3[i][s1[i]][s2[i]]++;
        p1[i][s1[i]]++;
        p2[i][s2[i]]++;
    }
}

int c[3][3];

int get_distance(int x, int y) {
    if (x == 0) {
        if (p1[y][0] != p2[y][0] || p1[y][1] != p2[y][1] || p1[y][2] != p2[y][2]) {
            return -1;
        }
    } else {
        if (p1[y][0] - p1[x - 1][0] != p2[y][0] - p2[x - 1][0] ||
            p1[y][1] - p1[x - 1][1] != p2[y][1] - p2[x - 1][1] ||
            p1[y][2] - p1[x - 1][2] != p2[y][2] - p2[x - 1][2]) {
            return -1;
        }
    }

    for (int i = 0; i <= 2; i++) {
        for (int j = 0; j <= 2; j++) {
            if (x == 0)
                c[i][j] = p3[y][i][j];
            else
                c[i][j] = p3[y][i][j] - p3[x - 1][i][j];
        }
    }

    int ans = 0;
    int all = y - x + 1;
    all -= c[0][0];
    all -= c[1][1];
    all -= c[2][2];
    int h = min(c[0][1], c[1][0]);
    ans += h;
    all -= 2*h;
    h = min(c[0][2], c[2][0]);
    ans += h;
    all -= 2*h;
    h = min(c[1][2], c[2][1]);
    ans += h;
    all -= 2*h;
    ans += (all / 3) * 2;

    return ans;
}

/*void stress(){
	srand(42);
	int n = 7;
	string s = "AT";
	while(true){
		string a, b;
		for(int i=0; i<n; i++){
			a += s[rand() % 2];
			b += s[rand() % 2];
		}
		init(a, b);
		my_init(a, b);
		for(int i=0; i<n-1; i++){
			for(int j=i; j<n-1; j++){
				if(get_distance(i, j) != my_get_distance(i, j)){
					cout << n << " 1\n";
					cout << a << "\n" << b << "\n" << i << " " << j << endl;
					cout << get_distance(i, j) << endl;
					return;
				}
			}
		}
	}
}

int main(){
	stress();
}*/

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