Submission #1059723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059723		vjudge1	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	8488 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int get_id(char c) { return c == 'A' ? 0 : c == 'C' ? 1 : 2; }

int n;
vi A, B;
vector<array<int, 9> > Fr;
void init(string a, string b) {
    n = a.size();
    for(auto it : a) A.push_back(get_id(it));
    for(auto it : b) B.push_back(get_id(it));
    Fr.resize(n);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 9; ++j)
            Fr[i][j] = i ? Fr[i - 1][j] : 0;
        ++Fr[i][A[i] * 3 + B[i]];
    }
}

int get_distance(int x, int y) {
    array<array<int, 3>, 3> Nr;
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j) Nr[i][j] = 0;
    for(int i = 0; i < 9; ++i) {
        int delta = Fr[y][i];
        if(x) delta -= Fr[x - 1][i];
        Nr[i / 3][i % 3] = delta;
    }
//    for(int i = 0; i < 3; ++i) {
//        for(int j = 0; j < 3; ++j) {
//            cout << Nr[i][j] << " ";
//        }
//        cout << "\n";
//    }
//    cout << "\n";
    array<int, 3> delta;
    for(int i = 0; i < 3; ++i) delta[i] = 0;
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j) {
            if(i != j) {
                delta[i] -= Nr[i][j];
                delta[j] += Nr[i][j];
            }
        }
    for(int i = 0; i < 3; ++i)
        if(delta[i]) return -1;
    int re = 0;
    for(int i = 0; i < 3; ++i)
        for(int j = i + 1; j < 3; ++j) {
            if(Nr[i][j] && Nr[j][i]) {
                int v = min(Nr[i][j], Nr[j][i]);
                Nr[i][j] -= v; Nr[j][i] -= v;
                re += v;
            }
        }
//    for(int i = 0; i < 3; ++i) {
//        for(int j = 0; j < 3; ++j) {
//            cout << Nr[i][j] << " ";
//        }
//        cout << "\n";
//    }
//    cout << "\n";
    vi P = {0, 1, 2};
    do {
        int v = n;
        for(int i = 0; i < 3; ++i) {
            int nxt = P[(i + 1) % 3];
            v = min(v, Nr[P[i]][nxt]);
        }
        re += 2 * v;
        for(int i = 0; i < 3; ++i) {
            int nxt = P[(i + 1) % 3];
            Nr[P[i]][nxt] -= v;
        }
    } while (next_permutation(P.begin(), P.end()));
//    for(int i = 0; i < 3; ++i) {
//        for(int j = 0; j < 3; ++j) {
//            cout << Nr[i][j] << " ";
//        }
//        cout << "\n";
//    }
//    cout << "\n";
    
	return re;
}

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