Submission #799070

#	Time	Username	Problem	Language	Result	Execution time	Memory
799070		TheSahib	Mutating DNA (IOI21_dna)	C++17	100 / 100	110 ms	18208 KiB

dna

#include <bits/stdc++.h>

#define ll long long
#define i128 __int128_t
#define pii pair<int, int>
#define oo 1e9
#define table array<array<int, 3>, 3>

using namespace std;

int n = 0;
string a, b;

vector<table> tree;

table combine(table t1, table t2){
    table ans;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            ans[i][j] = t1[i][j] + t2[i][j];
        }
    }
    return ans;
}

void build(int node, int l, int r){
    if(l == r){
        tree[node][a[l]][b[l]] = 1;
        return;
    }

    int mid = (l + r) / 2;
    build(node * 2 + 1, l, mid);
    build(node * 2 + 2, mid + 1, r);
    tree[node] = combine(tree[node * 2 + 1], tree[node * 2 + 2]);
}

table ask(int node, int l, int r, int ql, int qr){
    if(qr < l || r < ql){
        return table();
    }
    else if(ql <= l && r <= qr){
        return tree[node];
    }
    int mid = (l + r) / 2;
    return combine(ask(node * 2 + 1, l, mid, ql, qr), ask(node * 2 + 2, mid + 1, r, ql, qr));
}

void init(string s1, string s2){
    a = s1;
    b = s2;

    n = a.size();
    map<char,char> m = {{'A', 0}, {'C', 1}, {'T', 2}};
    for (int i = 0; i < n; i++)
    {
        a[i] = m[a[i]];
        b[i] = m[b[i]];
    }
    

    tree.resize(n * 4);
    build(0, 0, n - 1);
}

int get_distance(int x, int y){
    int ans = 0;
    int c = 0;
    table t = ask(0, 0, n - 1, x, y);
    for (int i = 0; i < 3; i++) t[i][i] = 0;
    
    int s = 0;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if(i == j) continue;
            int a = min(t[i][j], t[j][i]);
            ans += a;
            t[i][j] -= a;
            t[j][i] -= a;
            s += t[i][j];
        }
    }
    for (int i = 0; i < 3; i++)
    {
        int a = 0, b = 0;
        for (int j = 0; j < 3; j++)
        {
            a += t[i][j];
            b += t[j][i];
        }
        if(a != b){
            return -1;
        }
    }
    
    ans += s / 3 * 2;
    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:70:9: warning: unused variable 'c' [-Wunused-variable]
   70 |     int c = 0;
      |         ^

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