Submission #1041996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041996		0npata	Mutating DNA (IOI21_dna)	C++17	100 / 100	33 ms	7516 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>

using namespace std;

#define vec vector
#define arr array

const int MXN = 100'005;

arr<arr<int, 3>, 3> psum_pref[MXN+1];

void init(std::string a, std::string b) {
    map<char, int> chtoid; 
    chtoid['A'] = 0;
    chtoid['C'] = 1;
    chtoid['T'] = 2;

    int n = a.size();
    //cerr << a << '\n';

    for(int i = 1; i<=n; i++) {
        psum_pref[i] = psum_pref[i-1];
        psum_pref[i][chtoid[a[i-1]]][chtoid[b[i-1]]]++;
    }
}

int get_distance(int x, int y) {
    auto psum_range = psum_pref[y+1];
    arr<int, 3> a_cnt{0, 0, 0};
    arr<int, 3> b_cnt{0, 0, 0};
    for(int i = 0; i<3; i++) {
        for(int j = 0; j<3; j++) {
            psum_range[i][j] -= psum_pref[x][i][j];
            a_cnt[i] += psum_range[i][j];
            b_cnt[j] += psum_range[i][j];
        }
    }
    for(int i = 0; i<3; i++) {
        if(a_cnt[i] != b_cnt[i]) return -1;
    }
    int ans = 0;
    for(int i = 0; i<3; i++) {
        for(int j = i+1; j<3; j++) {
            int com = min(psum_range[i][j], psum_range[j][i]);
            ans += com;
            psum_range[i][j] -= com;
            psum_range[j][i] -= com;
        }
    }

    vec<int> rem(0);
    for(int i = 0; i<3; i++) {
        for(int j = 0; j<3; j++) {
            if(i == j) continue;
            if(psum_range[i][j] > 0) rem.push_back(psum_range[i][j]);
        }
    }
    assert(rem.size() <= 3);
    if(rem.size() == 0) return ans;
    if(rem.size() < 3) return -1;
    bool eq = rem[0] == rem[1] && rem[1] == rem[2];
    if(!eq) return -1;
    ans += rem[0]*2;
	return ans;
}

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