Submission #599316

#	Time	Username	Problem	Language	Result	Execution time	Memory
599316		lcj	Mutating DNA (IOI21_dna)	C++17	100 / 100	59 ms	9896 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define LSOne(S) ((S) & -(S))

struct Fenwick {
    vector<int> ft;
    Fenwick(int n) : ft(n+1, 0) {}
    int qry(int i) {
        int su = 0;
        for (; i > 0; i -= LSOne(i)) {
            su += ft[i];
        }
        return su;
    }
    int qry(int i, int j) {
        return qry(j)-qry(i-1);
    }
    void upd(int i, int dv) {
        for (; i < (int)ft.size(); i += LSOne(i)) {
            ft[i] += dv;
        }
    }
};

map<char, int> cmap = {
    {'A', 0},
    {'T', 1},
    {'C', 2}
};
vector<Fenwick> o1;
vector<Fenwick> o2;
vector<Fenwick> ts;

void init(string a, string b) {
    int n = a.size();
    o1.assign(3, Fenwick(n));
    o2.assign(3, Fenwick(n));
    ts.assign(9, Fenwick(n));
    for (int i = 0; i < n; i++)
    {
        if (a[i] == b[i]) continue;
        o1[cmap[a[i]]].upd(i+1, 1);
        o2[cmap[b[i]]].upd(i+1, 1);
        ts[cmap[a[i]]*3+cmap[b[i]]].upd(i+1, 1);
    }
}

int get_distance(int x, int y) {
    int su = 0;
    bool val = 1;
    vector<int> occ(9, 0);
    for (int i = 0; i < 9; i++)
    {
        occ[i] = ts[i].qry(x+1, y+1);
    }
    //sat 2 6 5 7
    int sub = 0;

    sub = min(occ[1], occ[3]);
    su += sub;
    occ[1] -= sub;
    occ[3] -= sub;

    sub = min(occ[2], occ[6]);
    su += sub;
    occ[2] -= sub;
    occ[6] -= sub;

    sub = min(occ[5], occ[7]);
    su += sub;
    occ[5] -= sub;
    occ[7] -= sub;

    for (int i = 0; i < 3; i++)
    {
        int out = 0;
        int ing = 0;
        for (int j = 0; j < 3; j++)
        {
            out += occ[i*3+j];
            ing += occ[j*3+i];
        }
        if (out != ing) {
            val = 0;
            break;
        }
    }
    if (!val) return -1;
    int esu = 0;
    for (int i = 0; i < 9; i++)
    {
        esu += occ[i];
    }
    su += (2*esu)/3;
    return su;
}

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