Submission #563567

#	Time	Username	Problem	Language	Result	Execution time	Memory
563567		rafatoa	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	9608 KiB

dna

#include <bits/stdc++.h>
using namespace std;

int n;
int pre[100005][3][3];
int cnta[100005][3];
int cntb[100005][3];

int ix(char c){
    if(c == 'A') return 0;
    else if(c == 'C') return 1;
    else return 2;
}

void init(string a, string b){
    n = a.size();

    for(int i=0; i<=n; i++)
        for(int j=0; j<3; j++){
            cnta[i][j] += cnta[i-1][j] + (ix(a[i-1]) == j ? 1 : 0);
            cntb[i][j] += cntb[i-1][j] + (ix(b[i-1]) == j ? 1 : 0);
        }

    for(int i=0; i<=n; i++)
        for(int j=0; j<3; j++)
            for(int k=0; k<3; k++)
                pre[i][j][k] += pre[i-1][j][k] + (ix(a[i-1]) == j && ix(b[i-1]) == k ? 1 : 0);
}

int get_distance(int x, int y){
    x++; y++;
    for(int j=0; j<3; j++)
        if(cnta[y][j]-cnta[x-1][j] != cntb[y][j]-cntb[x-1][j])
            return -1;

    int v[3][3];

    for(int j=0; j<3; j++)
    for(int k=0; k<3; k++)
        v[j][k] = pre[y][j][k] - pre[x-1][j][k];
    
    int ans = 0;

    for(int i=0; i<3; i++)
    for(int j=i+1; j<3; j++){
        if(v[i][j] >= v[j][i]){
            ans += v[j][i];
            v[i][j] -= v[j][i]; v[j][i] = 0;
        } else {
            ans += v[i][j];
            v[j][i] -= v[i][j]; v[i][j] = 0;
        }
    }

    // while(v[0][1] && v[1][2] && v[2][0]){
    //     v[0][1]--; v[1][2]--; v[2][0]--;
    //     ans += 2;
    // }

    // while(v[1][0] && v[2][1] && v[0][2]){
    //     v[1][0]--; v[2][1]--; v[0][2]--;
    //     ans += 2;
    // } 

    //ESTO ES MAS OPTIMO
    ans += v[0][1]*2 + v[1][0]*2;
    return ans;
}

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