Submission #1061394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061394		j_vdd16	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	8216 KiB

dna

#include "dna.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

int n;
vi a, b;
//vi prefixA[3], prefixB[3];
vi prefix[9];

void init(string A, string B) {
    n = (int)A.size();

    a = vi(n);
    b = vi(n);
    loop(i, n) {
        if (A[i] == 'A') a[i] = 0;
        if (A[i] == 'T') a[i] = 1;
        if (A[i] == 'C') a[i] = 2;

        if (B[i] == 'A') b[i] = 0;
        if (B[i] == 'T') b[i] = 1;
        if (B[i] == 'C') b[i] = 2;
    }

    loop(j, 9) prefix[j] = vi(n + 1);

    for (int i = 1; i <= n; i++) {
        loop(j, 9) {
            prefix[j][i] = prefix[j][i - 1];
        }

        prefix[a[i - 1] * 3 + b[i - 1]][i]++;
    }

    // loop(i, 3) {
    //     prefixA[i] = vi(n + 1);
    //     prefixB[i] = vi(n + 1);

    //     for (int j = 1; j <= n; j++) {
    //         prefixA[i][j] = prefixA[i][j - 1] + (a[j - 1] == i);
    //         prefixB[i][j] = prefixB[i][j - 1] + (b[j - 1] == i);
    //     }
    // }
}

int get_distance(int x, int y) {
    // loop(i, 3) {
    //     if (prefixA[i][y + 1] - prefixA[i][x] != prefixB[i][y + 1] - prefixB[i][x])
    //         return -1;
    // }

    int letterCounts[3] = { 0 };
    int counts[3][3] = { 0 };
    loop(j, 9) {
        counts[j / 3][j % 3] = prefix[j][y + 1] - prefix[j][x];
    }

    letterCounts[0] = counts[0][1] + counts[0][2] - counts[1][0] - counts[2][0];
    letterCounts[1] = counts[1][2] + counts[1][0] - counts[2][1] - counts[0][1];
    letterCounts[2] = counts[2][0] + counts[2][1] - counts[0][2] - counts[1][2];

    if (letterCounts[0] != 0 || letterCounts[1] != 0 || letterCounts[2] != 0) 
        return -1;

    int swap1 = min(counts[1][0], counts[0][1]);
    counts[1][0] -= swap1;
    counts[0][1] -= swap1;

    int swap2 = min(counts[2][0], counts[0][2]);
    counts[2][0] -= swap2;
    counts[0][2] -= swap2;

    int swap3 = min(counts[2][1], counts[1][2]);
    counts[2][1] -= swap3;
    counts[1][2] -= swap3;

    int result = swap1 + swap2 + swap3;
    int left = (y - x + 1) - 2 * (swap1 + swap2 + swap3) - counts[0][0] - counts[1][1] - counts[2][2];
    result += left / 3 * 2;

    return result;
}

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