제출 #1189619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189619		njoop	Mutating DNA (IOI21_dna)	C++20	0 / 100	20 ms	5632 KiB

dna

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

using namespace std;

int n, dp[100010][3][3];

void init(string a, string b) {
    n = a.size();
    for(int i=1; i<=n; i++) {
        int x, y;
        if(a[i-1] == 'C') x = 0;
        else if(a[i-1] == 'A') x = 1;
        else x = 2;
        if(b[i-1] == 'C') y = 0;
        else if(b[i-1] == 'A') y = 1;
        else y = 2;
        dp[i][x][y]++;
        for(int j=0; j<3; j++) {
            for(int k=0; k<3; k++) {
                dp[i][j][k] += dp[i-1][j][k];
            }
        }
    }
}

int get_distance(int x, int y) {
    x++; y++;
    int ans = 0;
    int ca = dp[y][0][1]-dp[x-1][0][1], ac = dp[y][1][0]-dp[x-1][1][0], ct = dp[y][0][2]-dp[x-1][0][2], tc = dp[y][2][0]-dp[x-1][2][0], at = dp[y][1][2]-dp[x-1][1][2], ta = dp[y][2][1]-dp[x-1][2][1];
    if(at+ac-ta-tc != 0 || tc+ta-at-ac != 0 || ca+ct-tc-ta != 0) return -1;
    
    int t = min(ta, at);
    ans += t; ta -= t; at -= t;
    t = min(ac, ca);
    ans += t; ac -= t; ca -= t;
    t = min(ct, tc);
    ans += t; ct -= t; tc -= t;
    ans += ((ac+at+ca+ct+ta+tc)*2)/3;
	return ans;
}

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