Submission #1246080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246080		sano	Mutating DNA (IOI21_dna)	C++20	0 / 100	228 ms	29908 KiB

dna

//#include "parks.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#include <variant>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

class intervalac {
    int n;
    vec<int> l, r, in;
    void update(int s) {
        in[s] = in[s * 2] + in[s * 2 + 1];
        return;
    }
public:
    void postav(int vel) {
        n = 1;
        while (n < vel) n *= 2;
        l.resize(2 * n); r.resize(2 * n); in.resize(2 * n, 0);
        For(i, n) {
            l[i + n] = r[i + n] = i;
        }
        rffor(i, 1, (n - 1)) {
            l[i] = l[i * 2];
            r[i] = r[i * 2 + 1];
        }
        return;
    }
    void zmen(int a, int b) {
        a += n;
        in[a] += b;
        a /= 2;
        while (a) {
            update(a);
            a /= 2;
        }
        return;
    }
    int daj(int a, int b, int s = 1) {
        if (l[s] > b || r[s] < a) return 0;
        if (a <= l[s] && r[s] <= b) return in[s];
        return daj(a, b, s * 2) + daj(a, b, s * 2 + 1);
    }
};

int n;
vec<intervalac> seg;
void init(string a, string b) {
    n = a.size();
    seg.resize(9);
    For(i, 9) {
        seg[i].postav(n);
    }
    For(i, n) {
        int hod = 0;
        if (a[i] == 'C') hod = 1;
        if (a[i] == 'T') hod = 2;
        hod *= 3;
        if (b[i] == 'C') hod++;
        if (b[i] == 'T') hod += 2;
        seg[hod].zmen(i, 1);
    }
    return;
}

int get_distance(int x, int y) {
    int vys = (y - x);
    vec<int> poc(9, 0);
    int pocital = 0;
    vec<int> pp1(3, 0), pp2(3, 0);
    For(i, 3) {
        For(j, 3) {
            int hod = i * 3 + j;
            poc[i*3 + j] = seg[hod].daj(x, y);
            pp1[i] += poc[i * 3 + j];
            pp2[j] += poc[i * 3 + j];
        }
    }
    For(i, 3) {
        vys -= poc[i * 3 + i];
        pocital++;
        if (pp1[i] != pp2[i]) {
            return -1;
        }
    }
    if (x == y) return 0;
    For(i, 3) {
        For(j, 3) {
            if (i == j) continue;
            int hod1 = poc[i * 3 + j];
            int hod2 = poc[j * 3 + i];
            int k = min(hod1, hod2);
            poc[i * 3 + j] -= k;
            poc[j * 3 + i] -= k;
            pocital += 2 * k;
            vys -= k;
        }
    }
    For(i, 3) {
        For(j, 3) {
            if (i == j) continue;
            int k = 0;
            for (; k < 3; k++) {
                if (k != i && k != j) break;
            }
            int hod1 = i * 3 + j;
            int hod2 = k * 3 + i;
            int hod3 = j * 3 + k;
            int mm = min(min(poc[hod1], poc[hod2]), poc[hod3]);
            poc[hod1] -= mm;
            poc[hod2] -= mm;
            poc[hod3] -= mm;
            pocital += 3 * mm;
            vys -= mm;
        }
    }
    if (pocital == (y-x + 1)) vys++;
    return vys;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    int q; cin >> q;
    string a, b; cin >> a >> b;
    init(a, b);
    For(i, q) {
        int x, y; cin >> x >> y;
        cout << get_distance(x, y) << '\n';
    }
    return 0;
}*/

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