제출 #1041968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041968		0npata	DNA 돌연변이 (IOI21_dna)	C++17	35 / 100	23 ms	7448 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();

    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];
    for(int i = 0; i<3; i++) {
        for(int j = 0; j<3; j++) {
            psum_range[i][j] -= psum_pref[x][i][j];
            //cerr << psum_range[i][j] << ' ';
        }
        //cerr << '\n';
    }
    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: 0 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16