Submission #1174262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174262		PagodePaiva	Mutating DNA (IOI21_dna)	C++20	100 / 100	29 ms	6152 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 100010;
int cnt[N][3][3];

void init(std::string a, std::string b) {
    for(int i = 1;i <= a.size();i++){
        int x = (a[i-1] == 'A' ? 0 : (a[i-1] == 'C' ? 1 : 2));
        int y = (b[i-1] == 'A' ? 0 : (b[i-1] == 'C' ? 1 : 2));
        for(int j = 0;j < 3;j++){
            for(int k = 0;k < 3;k++){
                cnt[i][j][k] = cnt[i-1][j][k];

            }
        }
        cnt[i][x][y]++;
    }
    return;
}

int get_distance(int x, int y) {
    x++;
    y++;
    int val[3][3];
    for(int j = 0;j < 3;j++){
        for(int k = 0;k < 3;k++){
            val[j][k] = cnt[y][j][k]-cnt[x-1][j][k];
           // cout << val[j][k] << ' ';
        }
        //cout << '\n';
    }
    int res = 0;
    for(int j = 0;j < 3;j++){
        for(int k = j+1;k < 3;k++){
            int t = min(val[j][k], val[k][j]);
            res += t;
            val[j][k] -= t;
            val[k][j] -= t;
        }
    }
    int t = min({val[0][1], val[1][2], val[2][0]});
    val[0][1] -= t;
    val[1][2] -= t;
    val[2][0] -= t;
    res += 2*t;
    t = min({val[0][2], val[2][1], val[1][0]});
    val[0][2] -= t;
    val[2][1] -= t;
    val[1][0] -= t;
    res += 2*t;
    for(int j = 0;j < 3;j++){
        for(int k = 0;k < 3;k++){
            if(j == k) continue;
            if(val[j][k] != 0) return -1;
        }
    }
    return res;
}

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