Submission #563760

#	Time	Username	Problem	Language	Result	Execution time	Memory
563760		kartel	Mutating DNA (IOI21_dna)	C++17	100 / 100	184 ms	8680 KiB

dna

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "dna.h"
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define el "\n"
using namespace std;

const int N = 2e5 + 500;

vector <int> in_a[26], in_b[26];
int pf[3][3][N];
int n;
vector <char> sb;

void init(string a, string b) {
    n = sz(a);
    map <char, int> mp;
    mp['A'] = 0;
    mp['C'] = 1;
    mp['T'] = 2;
    for (int i = 0; i < sz(a); i++) {
        in_a[a[i] - 'A'].pb(i);
        in_b[b[i] - 'A'].pb(i);
        pf[mp[a[i]]][mp[b[i]]][i]++;
    }
    for (int a = 0; a < 3; a++) {
        for (int b = 0; b < 3; b++) {
            for (int i = 1; i < n; i++) {
                pf[a][b][i] += pf[a][b][i - 1];
            }
        }
    }
    sb = {'A', 'C', 'T'};
}

int get_distance(int x, int y) {
    for (auto c : sb) {
        int L = lower_bound(all(in_a[c - 'A']), x) - in_a[c - 'A'].begin();
        int R = upper_bound(all(in_a[c - 'A']), y) - in_a[c - 'A'].begin();

        int l = lower_bound(all(in_b[c - 'A']), x) - in_b[c - 'A'].begin();
        int r = upper_bound(all(in_b[c - 'A']), y) - in_b[c - 'A'].begin();

        if (R - L != r - l) {
            return -1;
        }
    }


    vector <vector <int> > cnt(3, vector <int> (3, 0));
    for (int a = 0; a < 3; a++) {
        for (int b = 0; b < 3; b++) {
            cnt[a][b] = pf[a][b][y] - (x ? pf[a][b][x - 1] : 0);
        }
    }

    int ans = 0;
    for (int a = 0; a < 3; a++) {
        for (int b = 0; b < 3; b++) {
            if (a == b) {
                continue;
            }
            int cur = min(cnt[a][b], cnt[b][a]);
            ans += cur;
            cnt[a][a] += cur; cnt[a][b] -= cur;
            cnt[b][b] += cur; cnt[b][a] -= cur;
        }
    }

    int add = 0;
    for (int a = 0; a < 3; a++) {
        for (int b = 0; b < 3; b++) {
            if (a == b) {
                continue;
            }
            add += cnt[a][b];
        }
    }
    assert(add % 3 == 0);

    return ans + add - add / 3;
}

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