Submission #1262775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262775		tapilyoca	Mutating DNA (IOI21_dna)	C++20	0 / 100	42 ms	26436 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;

using ll = long long;
using str = string;

struct Ans {
    ll A, T, C;
    Ans() : A(0), T(0), C(0) {}
    Ans(ll a, ll t, ll c) {
        A = a; T = t; C = c;
    }

    bool operator!=(const Ans&two) const {
        return not(A == two.A and T == two.T and C == two.C);
    }

    Ans operator+(const Ans&two) const {
        return Ans(A+two.A, T+two.T, C+two.C);
    }

    Ans operator-(const Ans&two) const {
        return Ans(A-two.A,T-two.T,C-two.C);
    }
};

vec<Ans> aPref, bPref;
vec<vec<vec<ll>>> swaps; // swaps[i][a][b] = number of As that should swap to Bs

ll fuzz(char x) {
    if(x == 'A') return 0;
    if(x == 'T') return 1;
    return 2;
}

ll n;
void init(str a, str b) {
    n = a.length();
    aPref.resize(n);
    bPref.resize(n);
    swaps.assign(n, vector<vector<ll>>(3, vector<ll>(3,0ll)));

    for(int i = 0; i < n; i++) {

        if(a[i] == 'A') aPref[i] = {1,0,0};
        if(a[i] == 'T') aPref[i] = {0,1,0};
        if(a[i] == 'C') aPref[i] = {0,0,1};

        if(b[i] == 'A') bPref[i] = {1,0,0};
        if(b[i] == 'T') bPref[i] = {0,1,0};
        if(b[i] == 'C') bPref[i] = {0,0,1};

        if(i) {
            aPref[i] = aPref[i] + aPref[i-1];
            bPref[i] = bPref[i] + bPref[i-1];
        }

        ll aa = fuzz(a[i]);
        ll bb = fuzz(b[i]);
        swaps[i][aa][bb] = 1;
        // swaps[i][bb][aa] = 1;

        if(i) {
            for(int j = 0; j <= 2; j++) {
                for(int k = 0; k <= 2; k++) {
                    swaps[i][j][k] += swaps[i-1][j][k];
                }
            }
        }
    }
}

int get_distance(int x, int y) {

    Ans one = aPref[y] - (x ? aPref[x-1] : Ans(0,0,0));
    Ans two = bPref[y] - (y ? bPref[x-1] : Ans(0,0,0));
    if(one != two) return -1;


    ll ans = 0;
    bool flag = 0;

    for(int i = 0; i <= 2; i++) {
        for(int j = i+1; j <= 2; j++) {
            ll bleh = swaps[y][i][j] - (x ? swaps[x-1][i][j] : 0);
            ll blah = swaps[y][j][i] - (x ? swaps[x-1][j][i] : 0); 
            ans += min(bleh,blah);

            if(bleh > blah and not flag) {
                // then also need to make cyclic shift
                // cyclic shift costs 2 * diff
                ans += 2 * (bleh - blah);
                flag = 1;
            }
        }
    }

    return ans;    
}

/*(

ATACAT
ACTATA

TAC
CTA 
)*/

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