Submission #689467

#	Time	Username	Problem	Language	Result	Execution time	Memory
689467		coding_snorlax	Mutating DNA (IOI21_dna)	C++17	56 / 100	40 ms	3576 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
string A,B;
vector<int> prefix_dis={0};
vector<int> prefix_check={0};
void init(string a, string b){
    for(int i=0;i<(int)a.size();i++){
        if(a[i]!=b[i]){
            if(a[i]=='A') prefix_check.push_back(prefix_check.back()+1);
            else prefix_check.push_back(prefix_check.back()-1);
            prefix_dis.push_back(prefix_dis.back()+1);
        }
        else{
            prefix_check.push_back(prefix_check.back());
            prefix_dis.push_back(prefix_dis.back());
        }
    }
    A=a;
    B=b;
}
int get_distance(int x,int y){
    if(y-x<=2){
    if(y==x){
        if(A[x]==B[x]) return 0;
        else return -1;
    }
    else if(y==x+1){
        if(A[x]==B[x] && A[x+1]==B[x+1]) return 0;
        else if(A[x]==B[x+1] && A[x+1]==B[x]) return 1;
        else return -1;
    }
    else{
        if(A[x+2]==B[x+2]){
            if(A[x]==B[x] && A[x+1]==B[x+1]) return 0;
            else if(A[x]==B[x+1] && A[x+1]==B[x]) return 1;
            else return -1;
        }
        else if(A[x+1]==B[x+1]){
            if(A[x]==B[x] && A[x+2]==B[x+2]) return 0;
            else if(A[x]==B[x+2] && A[x+2]==B[x]) return 1;
            else return -1;
        }
        else if(A[x]==B[x]){
            if(A[x+1]==B[x+1] && A[x+2]==B[x+2]) return 0;
            else if(A[x+1]==B[x+2] && A[x+2]==B[x+1]) return 1;
            else return -1;
        }
        else{
            if(A[x]==B[x+1] && A[x+1]==B[x+2] && A[x+2]==B[x]) return 2;
            else if(A[x+1] == B[x] && A[x+2]==B[x+1] && A[x]==B[x+2]) return 2;
            else return -1;
        }
    }
    }
    /*
    int Count = 0;
    int find_answer = 0;

    for(int i=x;i<=y;i++){
        if(A[i]!=B[i]){
            if(A[i]=='A') find_answer++;
            else find_answer--;
            Count++;
        }
    }*/
    if(prefix_check[y+1]-prefix_check[x]) return -1;
    else return (prefix_dis[y+1]-prefix_dis[x])/2;
}

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