Submission #1312286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312286		opeleklanos	Mutating DNA (IOI21_dna)	C++20	100 / 100	30 ms	6452 KiB

dna

#include <iostream>
#include <vector>
#include "dna.h"
using namespace std;

string a;
string b;

vector<int> dp[3][3];

int curr[3][3];

void init(string a1, string b1){
    a = a1;
    b = b1;
    int n = a.size();
    for(int i = 0; i<n; i++){
        if(a[i] == 'T') a[i] = '0';
        else if(a[i] == 'C') a[i] = '1';
        else if(a[i] == 'A') a[i] = '2';
        if(b[i] == 'T') b[i] = '0';
        else if(b[i] == 'C') b[i] = '1';
        else if(b[i] == 'A') b[i] = '2';
    }
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++) dp[i][j].assign(n, 0);
    }
    for(int i = 0; i<n; i++){
        for(int ai = 0; ai<3; ai++){
            for(int bi = 0; bi<3; bi++){
                dp[ai][bi][i] = (i>0?dp[ai][bi][i-1]:0) + (a[i]-'0' == ai && b[i]-'0' == bi);
            }
        }
    }
}

int get_distance(int l, int r){
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){
            curr[i][j] = dp[i][j][r] - (l>0?dp[i][j][l-1]:0);
        }
    }
    
    int moves = 0;
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){
            if(i == j || curr[i][j] == 0) continue;
            if(curr[j][i] >= curr[i][j]){
                curr[j][i] -= curr[i][j];
                moves += curr[i][j];
                curr[i][j] = 0;
            }
            else{
                moves += curr[j][i];
                curr[i][j] -= curr[j][i];
                curr[j][i] = 0;
                int k = 0;
                while(k==j || k==i) k++;
                if(curr[k][i] < curr[i][j]) return -1;
                curr[k][i] -= curr[i][j];
                curr[k][j] += curr[i][j];
                moves += curr[i][j];
                curr[i][j] = 0;
            }
        }
    }

    return moves;
}

// int main(void){
//     freopen("input.txt", "r", stdin);
//     string a1, b1; 
//     int q;
//     cin>>a1>>b1>>q;
//     init(a1, b1);
//     for(int i = 0; i<q; i++){
//         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