Submission #1049542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049542		boyliguanhan	Mutating DNA (IOI21_dna)	C++17	100 / 100	23 ms	7444 KiB

dna

#include<bits/stdc++.h>
using namespace std;
int prefdif[3][100100],prefpairs[3][3][100100],stuf[128];
void init(std::string a, std::string b) {
    a=' '+a;
    b=' '+b;
    stuf['A']=1;
    stuf['C']=2;
    int n=a.size();
    for(int i=1;i<n;i++) {
        int A=a[i],B=b[i];
        A=stuf[A],B=stuf[B];
        prefpairs[A][B][i]++;
        prefdif[A][i]++;
        prefdif[B][i]--;
    }
    for(int i=0;i<3;i++)
        for(int j=1;j<n;j++)
            prefdif[i][j]+=prefdif[i][j-1];
    for(int i=0;i<9;i++) for(int j=1;j<n;j++)
        prefpairs[i/3][i%3][j]+=prefpairs[i/3][i%3][j-1];
}

int get_distance(int x, int y) {
    ++x;++y;
    if(prefdif[0][x-1]-prefdif[0][y])
        return -1;
    if(prefdif[1][x-1]-prefdif[1][y])
        return -1;
    if(prefdif[2][x-1]-prefdif[2][y])
        return -1;
    int ac=prefpairs[1][2][y]-prefpairs[1][2][x-1];
    int ca=prefpairs[2][1][y]-prefpairs[2][1][x-1];
    int at=prefpairs[1][0][y]-prefpairs[1][0][x-1];
    int ta=prefpairs[0][1][y]-prefpairs[0][1][x-1];
    int ct=prefpairs[2][0][y]-prefpairs[2][0][x-1];
    int tc=prefpairs[0][2][y]-prefpairs[0][2][x-1];
    int ANS=min(ac,ca)+min(at,ta)+min(ct,tc);
	return ANS+(ac+ca+at+ta+ct+tc-2*ANS)/3*2;
}

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