제출 #1251251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251251		FernandoJC07	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	35 ms	9800 KiB

dna

#include <bits/stdc++.h>
#define vi vector<int>
#define vii vector<vi>
#define ff first
#define ss second
#define For(i, a, n) for(int i = a; i<n; ++i)
using namespace std;

unordered_map<char, int> ump;
vii ps;

int cod(int a, int b){ return a+3*b;}
pair<int, int> dec(int a){ return {a%3, a/3};}
int idec(int a) {return cod(dec(a).ss, dec(a).ff);}

void init(string a, string b){
    int n = a.size();
    ump['A'] = 0; ump['C'] = 1; ump['T'] = 2;
    ps.resize(n+1, vi(9, 0));
    For(i, 0, n){
        ps[i+1] = ps[i];
        ps[i+1][cod(ump[a[i]], ump[b[i]])]++;
    }
}

int get_distance(int x, int y){
    ++x; ++y;
    vi v(9);
    For(i, 0, 9) v[i] = ps[y][i] - ps[x-1][i];
    vi a(3, 0), b(3, 0);
    For(i, 0, 9){
        auto s = dec(i);
        a[s.ff] += v[i]; b[s.ss] += v[i];
    }
    if(a != b) return -1;
    int n = y-x+1;
    int t = n - v[0] - v[4] - v[8];
    int p = t-n; For(i, 0, 9) p += min(v[i], v[idec(i)]);
    int ans = (4*t - p)/6;
    return ans;
}

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