제출 #1000037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000037		codefox	DNA 돌연변이 (IOI21_dna)	C++17	56 / 100	32 ms	5920 KiB

dna

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

using namespace std;

vector<int> AC;
vector<int> AT;
vector<int> CA;
vector<int> CT;
vector<int> TA;
vector<int> TC;

void init(string a, string b)
{
    int n = a.size();
    AC.assign(n+1, 0);
    AT.assign(n+1, 0);
    CA.assign(n+1, 0);
    CT.assign(n+1, 0);
    TA.assign(n+1, 0);
    TC.assign(n+1, 0);
    for (int i = 0; i < n; i++)
    {
        AC[i+1] = AC[i];
        AT[i+1] = AT[i];
        CA[i+1] = CA[i];
        CT[i+1] = CT[i];
        TA[i+1] = TA[i];
        TC[i+1] = TC[i];
        if (a[i]=='A')
        {
            if (b[i]=='C') AC[i+1]++;
            if (b[i]=='T') AT[i+1]++;
        }
        if (a[i]=='C')
        {
            if (b[i]=='A') CA[i+1]++;
            if (b[i]=='T') CT[i+1]++;
        }
        if (a[i]=='T')
        {
            if (b[i]=='A') TA[i+1]++;
            if (b[i]=='C') TC[i+1]++;
        }
    }
}


int get_distance(int y, int x)
{
    int sol = 0;
    int ac = AC[x+1]-AC[y];
    int at = AT[x+1]-AT[y];
    int ca = CA[x+1]-CA[y];
    int ct = CT[x+1]-CT[y];
    int ta = TA[x+1]-TA[y];
    int tc = TC[x+1]-TC[y];
    if (ac+at != ta+ca) return -1;
    if (ca+ct != tc+ac) return -1;
    if (ta+tc != at+ct) return -1;
    sol += min(ac, ca) +min(at, ta) + min(ct, tc);
    ac -= min(ac, ca);
    at -= min(at, ta);
    ca -= min(ac, ca);
    ct -= min(tc, ct);
    ta -= min(at, ta);
    tc -= min(tc, ct);
    vector<int> nn;
    if (ac != 0) nn.push_back(ac);
    if (at != 0) nn.push_back(at);
    if (ca != 0) nn.push_back(ca);
    if (ct != 0) nn.push_back(ct);
    if (ta != 0) nn.push_back(ta);
    if (tc != 0) nn.push_back(tc);
    sort(nn.begin(), nn.end());
    if (nn.size() > 2) sol += nn[1] + nn[0];
    return sol;
}

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