Submission #1197050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197050		cpdreamer	Mutating DNA (IOI21_dna)	C++20	100 / 100	22 ms	5024 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 pref1[(int)1e5+1][6];
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<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++;
    int ans=0;
    int c=0;
    int c1a=(pref1[y][0]+pref1[y][2]-pref1[x][0]-pref1[x][2]);
    int c2a=(pref1[y][1]+pref1[y][4]-pref1[x][1]-pref1[x][4]);
    int c3a=(pref1[y][3]+pref1[y][5]-pref1[x][3]-pref1[x][5]);
    int c1b=(pref1[y][1]+pref1[y][3]-pref1[x][1]-pref1[x][3]);
    int c2b=(pref1[y][0]+pref1[y][5]-pref1[x][0]-pref1[x][5]);
    int c3b=(pref1[y][2]+pref1[y][4]-pref1[x][2]-pref1[x][4]);
    for (int j=0,i=0;j<6;j+=2,i++) {
        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);
    }
    if ((c1b!=c1a) || (c2b!=c2a) || (c3b!=c3a)) {
        return -1;
    }
    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