Submission #1231307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231307		coco2311	Mutating DNA (IOI21_dna)	C++17	0 / 100	25 ms	2304 KiB

dna

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int N;
char a[100001],b[100001];

void init(string a2, string b2){
    N=a2.size();
    for(int i=0;i<N;i++){
        a[i]=a2[i];
        b[i]=b2[i];
    }
}

int get_distance(int x,int y){
    int a1[3]={0},b1[3]={0};
    for(int i=x;i<=y;i++){
        if(a[i]=='A'){
            a1[0]++;
        }
        else if(a[i]=='C'){
            a1[1]++;
        }
        else{
            a1[2]++;
        }
        if(b[i]=='A'){
            b1[0]++;
        }
        else if(a[i]=='C'){
            b1[1]++;
        }
        else{
            b1[2]++;
        }
    }
    for(int i=0;i<3;i++){
        if(a1[i]!=b1[i]){
            return -1;
        }
    }
    stack<int> wa,wc,wt; //index of wrong letter
    for(int i=y;i>=x;i--){
        if(a[i]==b[i])continue;
        if(b[i]=='A'){
            wa.push(i);
        }
        else if(b[i]=='C'){
            wc.push(i);
        }
        else{
            wt.push(i);
        }
    }
    int d=0;
    for(int i=x;i<=y;i++){
        if(a[i]==b[i])continue;
        d++;
        if(a[i]=='A'){
            b[wa.top()]=b[i];
            wa.pop();
        }
        else if(a[i]=='C'){
            b[wc.top()]=b[i];
            wc.pop();
        }
        else{
            b[wt.top()]=b[i];
            wt.pop();
        }

        if(b[i]=='A'){
            wa.pop();
        }
        else if(b[i]=='C'){
            wc.pop();
        }
        else{
            wt.pop();
        }

    }
    return d;
}

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