Submission #586935

#	Time	Username	Problem	Language	Result	Execution time	Memory
586935		MadokaMagicaFan	Mutating DNA (IOI21_dna)	C++17	100 / 100	55 ms	13284 KiB

dna

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
/* #define ONPC */

struct sump {
    int n;
    vector<int> a;
    vector<int> tr;

    sump() {}

    void
    set(int _n) {
        n = _n;
        a.assign(n,0);
        tr.assign(n,0);
    }

    void
    add(int x)
    {
        ++a[x];
        return;
    }

    void
    gen()
    {
        for (int i = 0; i < n; ++i) {
            if (i) tr[i] = tr[i-1];
            tr[i] += a[i];
        }
        return;
    }

    int
    query(int x)
    {
        if (x < 0)
            return 0;
        return tr[x];
    }

    int
    query(int l, int r)
    {
        return query(r) - query(l-1);
    }
};

sump aa, at, ac;
sump ba, bt, bc;

sump t[6];

void
init(string a, string b)
{
    int n = sz(a);
    aa.set(n);
    at.set(n);
    ac.set(n);
    ba.set(n);
    bt.set(n);
    bc.set(n);

    for (int i = 0; i < 6; ++i) t[i].set(n);

    for (int i = 0; i < n; ++i) {
        if (a[i] == 'A') {
            aa.add(i);
            if (b[i] == 'C') t[0].add(i);
            if (b[i] == 'T') t[1].add(i);
        }

        if (a[i] == 'C') {
            ac.add(i);
            if (b[i] == 'A') t[2].add(i);
            if (b[i] == 'T') t[3].add(i);
        }

        if (a[i] == 'T') {
            at.add(i);
            if (b[i] == 'A') t[4].add(i);
            if (b[i] == 'C') t[5].add(i);
        }
        if (b[i] == 'A') ba.add(i);
        if (b[i] == 'C') bc.add(i);
        if (b[i] == 'T') bt.add(i);
    }


    aa.gen();
    at.gen();
    ac.gen();
    ba.gen();
    bt.gen();
    bc.gen();
    for (int i = 0; i < 6; ++i) t[i].gen();

    return;
}

int
get_distance(int x, int y)
{
    int v[6];

    if (aa.query(x,y) != ba.query(x,y)) return -1;
    if (ac.query(x,y) != bc.query(x,y)) return -1;
    assert(at.query(x,y) == bt.query(x,y));
    if (at.query(x,y) != bt.query(x,y)) return -1; /* USELESS */

    for (int i = 0; i < 6; ++i) {
        v[i] = t[i].query(x,y);
    }

    int ans = 0;

    int a, b, c;

    a = min(v[0], v[2]);
    b = min(v[1], v[4]);
    c = min(v[3], v[5]);

    v[0] -= a;
    v[2] -= a;
    v[1] -= b;
    v[4] -= b;
    v[3] -= c;
    v[5] -= c;

    ans = a + b + c;

    ans += (v[0]<<1);
    ans += (v[1]<<1);

    return ans;
}


#ifdef ONPC
void
solve()
{
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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