Submission #1237668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237668		fauntleroy	Mutating DNA (IOI21_dna)	C++20	100 / 100	24 ms	6152 KiB

dna

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <limits>
#include <tuple>
#include <stack>
#include <bitset>
#include <cstring>
#include <sstream>
#include <functional>
#include <random>
#include "dna.h"
using namespace std;

const int mxn = 100000;
int pref[mxn][3][3];

int get(char c) {
    if (c == 'A')
        return 0;
    if (c == 'T')
        return 1;
    return 2;
}

void init(string a, string b) {
    int n = a.size();
    for (int x = 0; x < 3; ++x)
        for (int y = 0; y < 3; ++y)
            pref[0][x][y] = 0;

    pref[0][get(a[0])][get(b[0])] = 1;
    for (int i = 1; i < n; ++i) {
        int u = get(a[i]), v = get(b[i]);
        for (int x = 0; x < 3; ++x)
            for (int y = 0; y < 3; ++y)
                pref[i][x][y] = pref[i - 1][x][y];
        pref[i][u][v]++;
    }
}

int get_distance(int l, int r) {
    int cnt[3][3];
    for (int x = 0; x < 3; ++x) 
        for (int y = 0; y < 3; ++y) 
            cnt[x][y] = pref[r][x][y] - (l > 0 ? pref[l - 1][x][y] : 0);
    
    for (int c = 0; c < 3; ++c) {
        int o = cnt[c][0] + cnt[c][1] + cnt[c][2];
        int i = cnt[0][c] + cnt[1][c] + cnt[2][c];
        if (o != i) 
            return -1;
    }

    int ans = 0;
    for (int x = 0; x < 3; ++x) {
        for (int y = x + 1; y < 3; ++y) {
            int d = min(cnt[x][y], cnt[y][x]);
            ans += d;
            cnt[x][y] -= d;
            cnt[y][x] -= d;
        }
    }
    for (int d = 0; d < 3; ++d)
         cnt[d][d] = 0;
    int k = 0;
    for (int x = 0; x < 3; ++x)
        for (int y = 0; y < 3; ++y)
            k += cnt[x][y];
    ans += 2 * k / 3;
    return ans;
}

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