Submission #805504

#	Time	Username	Problem	Language	Result	Execution time	Memory
805504		7mody	Mutating DNA (IOI21_dna)	C++17	100 / 100	151 ms	43024 KiB

dna

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

const int maxn=1e5+10;
vector<vector<vector<int>>> pre(maxn, vector<vector<int>>(3, vector<int>(3))),check(maxn, vector<vector<int>>(3, vector<int>(3)));
int n;

void init(string a, string b){
    string s1=" " +a,s2= " " +b;
    n=s1.size()-1;
    for(int i=1; i <= n;i++){
        if(s1[i]=='T') s1[i]='B';
        if(s2[i]=='T') s2[i]='B';
    }
    for(int i=1; i <= n;i++){
        check[i]=check[i-1];
        int a=s1[i]-'A';
        int b=s2[i]-'A';
        check[i][1][a]++;
        check[i][2][b]++;
        pre[i]=pre[i-1];
        pre[i][a][b]++;
    }
}

int get_distance(int l, int r){
    r++;l++;
    vector<vector<int>> curr(3, vector<int>(3));
    for(int j=0; j < 3;j++){
        if(check[r][1][j]-check[l-1][1][j]!=check[r][2][j]-check[l-1][2][j]){
            return -1;
        }
    }
    for(int i=0; i < 3;i++){
        for(int j=0; j < 3;j++){
            curr[i][j]=pre[r][i][j]-pre[l-1][i][j];
        }
    }
    int answer=0;
    int current=r-l+1;
    for(int i=0; i < 3;i++){
        current-=curr[i][i];
    }
    for(int i=0; i < 3;i++){
        for(int j=i+1; j < 3;j++){
            int here=min(curr[i][j],curr[j][i]);
            current-=2*here;
            answer+=here;
            curr[i][j]-=here;
            curr[j][i]-=here;
        }
    }
    answer+=(current/3)*2;
    return answer;
}

// int main(){
//     string s1,s2; cin >> s1 >> s2;
//     init(s1,s2);
//     int q; cin >> q;
//     while(q--){
//         int l,r; cin >> l >> r;
//         cout << get_distance(l,r) << endl;
//     }
// }

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