Submission #818165

#	Time	Username	Problem	Language	Result	Execution time	Memory
818165		PixelCat	Mutating DNA (IOI21_dna)	C++17	100 / 100	34 ms	6948 KiB

dna

#include "dna.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

namespace {

const int MAXN = 100'000;

int n;
int pre[3][3][MAXN + 10];
int ca[3], cb[3];
int cnt[3][3];

int ch2int(char ch) {
    if(ch == 'A') return 0;
    if(ch == 'T') return 1;
    if(ch == 'C') return 2;
    assert(false);
    return -1;
}

void _init(string a, string b) {
    n = sz(a);
    For(c1, 0, 2) For(c2, 0, 2) pre[c1][c2][0] = 0;
    For(i, 1, n) {
        For(c1, 0, 2) For(c2, 0, 2) pre[c1][c2][i] = pre[c1][c2][i - 1];
        int cha = ch2int(a[i - 1]);
        int chb = ch2int(b[i - 1]);
        pre[cha][chb][i]++;
    }
}

int _get_distance(int l, int r) {
    memset(ca, 0, sizeof(ca));
    memset(cb, 0, sizeof(cb));
    For(c1, 0, 2) For(c2, 0, 2) {
        cnt[c1][c2] = pre[c1][c2][r] - pre[c1][c2][l - 1];
        ca[c1] += cnt[c1][c2];
        cb[c2] += cnt[c1][c2];
    }

    For(c, 0, 2) if(ca[c] != cb[c]) return -1;

    int ans = 0;

    auto owo = [&](int a, int b) {
        int k = min(cnt[a][b], cnt[b][a]);
        cnt[a][b] -= k;
        cnt[b][a] -= k;
        ans += k;
    };
    owo(0, 1);
    owo(0, 2);
    owo(1, 2);

    return ans + max(cnt[0][1], cnt[1][0]) * 2;
}

}

void init(string a, string b) {
    ::_init(a, b);
}

int get_distance(int x, int y) {
    return ::_get_distance(x + 1, y + 1);
}

/*

6 3
ATACAT
ACTATA
1 3
4 5
3 5

2
1
-1

*/

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