Submission #821779

#	Time	Username	Problem	Language	Result	Execution time	Memory
821779		HorizonWest	Mutating DNA (IOI21_dna)	C++17	100 / 100	84 ms	29076 KiB

dna

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 5e3 + 7, Inf = 2e8 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

vector <vector <int>> s;
vector <vector <vector<int>>> f;

void init(string a, string b)
{
    int n = (int) a.size(); string ref = "ATC";

    map <char, int> mp;

    for(int i = 0; i < (int) ref.size(); i++)
        mp[ref[i]] = i;

    s.assign(n + 1, vector <int> ((int) ref.size() + 1, 0));

    for(int i = 0; i < n; i++)
    {
        s[i][mp[a[i]]]++; s[i][mp[b[i]]]--;
        for(int j = 0; j < (int) ref.size(); j++)
            s[i][j] += (i > 0 ? s[i-1][j] : 0);
    }

    f.assign(n + 1, vector <vector<int>> (3, vector <int> (3, 0)));
    for(int i = 0; i < n; i++)
    {
        int _a = mp[a[i]], _b = mp[b[i]];
        f[i][_a][_b]++;
        for(int j = 0; j < 3; j++) if(i > 0)
            for(int k = 0; k < 3; k++)
                f[i][j][k] += f[i-1][j][k];
    }
}

int get_distance(int x, int y)
{
    bool can = true;
    for(int i = 0; i < 3; i++)
    {
        int t = s[y][i];
        if(x != 0) t -= s[x-1][i];
        if(t != 0) can = false;
    }

    int ans = 0, cont = 0;

    for(int i = 0; i < 3; i++)
    {
        for(int j = i + 1; j < 3; j++)
        {
            int t1 = 0, t2 = 0;
            if(x > 0)
            {
                t1 = f[x-1][i][j];
                t2 = f[x-1][j][i];
            }
            ans += min(f[y][i][j] - t1, f[y][j][i] - t2);
            cont += abs((f[y][i][j] - t1) - (f[y][j][i] - t2));
        }
    }

    cont /= 3; ans += cont * 2;

    return (can ? ans : -1);
}

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