Submission #1142250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142250		programming23	Mutating DNA (IOI21_dna)	C++20	0 / 100	551 ms	34852 KiB

dna

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

string stringA="";
string stringB="";
vector<int> arrCount;
vector<vector<map<char, int>>> mapCount;

void init(string a, string b) {
	stringA = a;
	stringB = b;
    int ln = stringA.size();
    arrCount.resize(ln, 0);
    mapCount.resize(ln);
    int count = 0;
    int cA = 0;
    int cT = 0;

    int cA2 = 0;
    int cT2 = 0;
    for(int i=ln-1; i>=0;i--){
        if (stringA[i] != stringB[i]){
            count+=1;
        }
        if(stringA[i] == 'A'){
            cA +=1;
        }else if(stringA[i] == 'T'){
            cT+=1;
        }

        if(stringB[i] == 'A'){
            cA2 +=1;
        }else if(stringB[i] == 'T'){
            cT2+=1;
        }
        mapCount[i] = {
            { {'A', cA}, {'T', cT} },
            { {'A', cA2}, {'T', cT2} }
        };
        arrCount[i] = count;
    }
    
}

int get_distance(int x, int y) {
	string sA = stringA;
	string sB = stringB;
    int ln = sA.size();
    int countBa = mapCount[x][1]['A'] - mapCount[min(ln, y+1)][1]['A'];
    int countBt = mapCount[x][1]['T'] - mapCount[min(ln, y+1)][1]['T'];

    int countBa1 = mapCount[x][0]['A'] - mapCount[min(ln, y+1)][0]['A'];
    int countBt1 = mapCount[x][0]['T'] - mapCount[min(ln, y+1)][0]['T'];
	map<char, int> countsB = {
        {'A', countBa},
        {'T', countBt},
    };
    if(countBa + countBt != y-x){
        countsB['C'] = max(countBa, countBt) - min(countBa, countBt);
    }
    map<char, int> countsA = {
        {'A', countBa1},
        {'T', countBt1},
    };
    if(countBa1 + countBt1 != y-x){
        countsA['C'] = max(countBa1, countBt1) - min(countBa1, countBt1);
    }
	int count = 0;
    int lnA = countsA.size();
    int lnB = countsB.size();


	if(lnA != lnB){
		return -1;
	}for(auto c: countsA){
		if(countsA[c.first] != countsB[c.first]){
			return -1;
		}
	}
    if(lnA == 2 && lnB == 2){
        count = arrCount[x];
        if(y+1 < ln){
            count-=arrCount[y+1];
        }
        return count/2;
    }

    int i=x;
    while (i <= y && sA != sB){
        char c = sA[i];
        if(c == sB[i]){
            i++;
            continue;
        }
        for(int z=i+1; z <= y; z++){
            if(sA[z] != sB[i] || sA[z] == sB[z]){
                continue;
            }
            sA[i] = sA[z];
            sA[z] = c;
            i++;
            count++;
        }
    }
	return count;
}

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