Submission #599288

#	Time	Username	Problem	Language	Result	Execution time	Memory
599288		lcj	Mutating DNA (IOI21_dna)	C++17	0 / 100	93 ms	8612 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
    su += min(occ[1], occ[3]);
    occ[1] = max(0, occ[1]-occ[3]);
    occ[3] = max(0, occ[3]-occ[1]);

    su += min(occ[2], occ[7]);
    occ[2] = max(0, occ[2]-occ[7]);
    occ[7] = max(0, occ[7]-occ[2]);

    su += min(occ[5], occ[8]);
    occ[2] = max(0, occ[5]-occ[8]);
    occ[7] = max(0, occ[8]-occ[5]);

    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 = -1;
    for (int i = 0; i < 9; i++)
    {
        esu += occ[i];
    }
    if (esu > 0) {
        su += esu;
    }
    return su;
}

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