Submission #1111873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111873		Zflop	Mutating DNA (IOI21_dna)	C++17	35 / 100	25 ms	8216 KiB

dna

#include <bits/stdc++.h>
using namespace std;
const int NMAX = (int)1e5 * 2;
int sum[NMAX][3][3],N;

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

void init(std::string a, std::string b) {
    N = a.size();
    for (int i = 1; i <= N;++i) {
        for (int x = 0; x < 3;++x)
            for (int y = 0; y < 3;++y)
                sum[i][x][y] += sum[i - 1][x][y];
        sum[i][get(a[i - 1])][get(b[i - 1])]++;
    }
}
int get_distance(int x, int y) {
    ++x,++y;
    int ans = 0;
    vector<vector<int>>v;
    for (int a = 0; a < 3;++a)
        for (int b = a + 1; b < 3;++b) {
            int one = sum[y][a][b] - sum[x - 1][a][b];
            int two = sum[y][b][a] - sum[x - 1][b][a];
            int g = min(one,two);
            if (g != max(one,two)) {
                if(one > two) v.push_back({a,b,one - two});
                else v.push_back({b,a,two - one});
            }
            ans += g;
        }
    if (v.size() == 0) return ans;
    if (v.size() == 1) return -1;
    if (v.size() == 2) {
        if (v[0][0] != v[1][1] || v[0][2] != v[1][2]) return -1;
        return ans + v[0][2];
    }
    if (v.size() == 3) {
        sort(v.begin(),v.end(),[&](vector<int>a,vector<int>b) {return a[2] < b[2];});
        ans += v[0][2] + (v[1][2] + v[2][2]) / 2;
        //cout << v[0][2] << ' ' << v[1][2] << ' ' << v[2][2] << '\n';
        if ((v[1][2] + v[2][2]) % 2) return -1;
        return ans;
        }
    return 0;
}

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