Submission #735807

#	Time	Username	Problem	Language	Result	Execution time	Memory
735807		NatInTheHat	Mutating DNA (IOI21_dna)	C++17	100 / 100	57 ms	7628 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<class T, class U> istream& operator>>(istream &is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T> istream& operator>>(istream& is, vector<T>& vec) { for(auto &x : vec) cin >> x; return is; } 
template<class T, class U> ostream& operator<<(ostream &os, pair<T, U>& p) { os << "<" << p.first << "," << p.second << ">"; return os; }
template<class T> ostream& operator<<(ostream& os, vector<T>& vec) { for(auto x : vec) os << x << " "; return os; }

int conv(char c) {
    if (c == 'A') return 0;
    else if (c == 'C') return 1;
    return 2;
}
const int TYPES = 9, MAXN = 100010;
int prefs[TYPES][MAXN];
int n;

void init(string sa, string sb) {
    n = sa.size();

    vector<int> a(n), b(n);
    
    for (int i = 0; i < n; i++) {
        a[i] = conv(sa[i]);
        b[i] = conv(sb[i]);
    }

    for (int i = 0; i < n; i++) {
        int type = a[i] * 3 + b[i];
        prefs[type][i]++;

        if (i > 0) {
            for (int t = 0; t < TYPES; t++) {
                prefs[t][i] += prefs[t][i-1];
            }
        }
    }
}
int get_sum(int type, int l, int r) {
    if (l == 0) return prefs[type][r];
    return prefs[type][r] - prefs[type][l-1];
}

const vector<int> refl = {0,3,6,1,4,7,2,5,8};

pair<int, int> comb(int x, int y) {
    pair<int, int> res;

    int xi = x / 3, xj = x % 3;
    int yi = y / 3, yj = y % 3;

    res.first = xi * 3 + yj;
    res.second = yi * 3 + xj;

    return res;
}

int get_distance(int l, int r) {
    vector<int> type_sums(TYPES);
    for (int t = 0; t < TYPES; t++) {
        type_sums[t] = get_sum(t, l, r);
    }
    int swaps = 0;

    // cancel out on diagonal.
    
    swaps += min(type_sums[1], type_sums[3]);
    swaps += min(type_sums[2], type_sums[6]);
    swaps += min(type_sums[5], type_sums[7]);

    vector<int> rems = {
        type_sums[1] - type_sums[3],
        type_sums[2] - type_sums[6],
        type_sums[5] - type_sums[7]
    };

    if (abs(rems[0]) == abs(rems[1]) && abs(rems[1]) == abs(rems[2])) {
        if (rems[0] == 0) return swaps;

        // if all the same sign, that's not good

        int ct = 0;
        for (int x = 0; x <= 2; x++) ct += rems[x] / abs(rems[x]);
        if (abs(ct) == 3) return -1;

        // is there a pair that we can combine
        // such that it is a reflection of the third thing?

        vector<int> elems;
        if (rems[0] > 0) elems.push_back(1);
        else elems.push_back(3);
        if (rems[1] > 0) elems.push_back(2);
        else elems.push_back(6);
        if (rems[2] > 0) elems.push_back(5);
        else elems.push_back(7);

        for (int x = 0; x <= 2; x++) {
            // x is the third thing
            int target = refl[elems[x]];
            int i = 0, j = 0;
            while (i == x) i++;
            while (j == i || j == x) j++;

            pair<int, int> combination = comb(elems[i], elems[j]);
            if (combination.first == target || combination.second == target) {
                return swaps + abs(rems[0]) * 2;
            }
        }
        return -1;
    }
    else return -1;
}

// int main() {
//     int n, q; cin >> n >> q;
//     string sa, sb; cin >> sa >> sb;
//     init(sa, sb);

//     for (int qq = 0; qq < q; qq++) {
//         int l, r; cin >> l >> r;
//         cout << get_distance(l, r) << '\n';
//     }
//     return 0;
// }

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