Submission #1197042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197042		cpdreamer	Mutating DNA (IOI21_dna)	C++20	35 / 100	23 ms	5028 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 cnt[3]={0,0,0};
    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);
        cnt[i]+=max(a,b)-min(a,b);
    }
    for (int i=0;i<3;i++) {
        for (int j=0;j<3;j++) {
            if (cnt[i]!=cnt[j])return-1;
        }
    }
    ans+=(2*c)/3;
    return ans;
}

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