제출 #1197028

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

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair
#define S second
#define F first
#define V vector
int pref_a[(int)1e5+1][3];
int pref_b[(int)1e5+1][3];
int pref1[(int)1e5+1][6];
V<char>v1={'A','T','C'};
V<P<char,char>>v2={{'A','T'},{'T','A'},{'A','C'},{'C','A'},{'T','C'},{'C','T'}};
void init(string a, string b) {
    a='.'+a;
    b='.'+b;
    int n=(int)a.size()-1;
    for (int i=1;i<=n;i++) {
        for (int j=0;j<3;j++) {
            pref_a[i][j]=pref_a[i-1][j];
            pref_b[i][j]=pref_b[i-1][j];
            if(a[i]==v1[j]) {
                pref_a[i][j]++;
            }
            if (b[i]==v1[j]) {
                pref_b[i][j]++;
            }
        }
        for (int j=0;j<6;j++) {
            pref1[i][j]=pref1[i-1][j];
            if (a[i]==v2[j].F && b[i]==v2[j].S) {
                pref1[i][j]++;
            }
        }
    }
}
int get_distance(int x, int y) {
    y++;
    for (int j=0;j<3;j++) {
        if (pref_a[y][j]-pref_a[x][j]!=pref_b[y][j]-pref_b[x][j]) {
            return -1;
        }
    }
    int ans=0;
    int c=0;
    for (int j=0;j<6;j+=2) {
        int a=pref1[y][j]-pref1[x][j];
        int b=pref1[y][j+1]-pref1[x][j+1];
        ans+=min(a,b);
        c+=max(a,b)-min(a,b);
    }
    ans+=(2*c)/3;
    return ans;
}

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