Submission #1281305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281305		imarn	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	24 ms	8436 KiB

dna

//#include "festival.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define sz(x) (ll)x.size()
#define cd complex<double>
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=1e5+5,inf=998244353;
int n;
int qs[2][mxn][3]{0},dp[mxn][3][3]{0};
void init(string a, string b){
    n=a.size();vector<char>id={'A','C','T'};
    for(int i=0;i<n;i++){
        qs[0][i+1][0]=qs[0][i][0]+(a[i]=='A');
        qs[0][i+1][1]=qs[0][i][1]+(a[i]=='C');
        qs[0][i+1][2]=qs[0][i][2]+(a[i]=='T');
        qs[1][i+1][0]=qs[1][i][0]+(b[i]=='A');
        qs[1][i+1][1]=qs[1][i][1]+(b[i]=='C');
        qs[1][i+1][2]=qs[1][i][2]+(b[i]=='T');
        for(int j=0;j<3;j++)for(int k=0;k<3;k++){
            dp[i+1][j][k]=dp[i][j][k]+(a[i]==id[j]&&b[i]==id[k]);
        }
    }
}
int get_distance(int x, int y){
    x++,y++;bool ch=0;int tt[3][3],cur[3];
    for(int i=0;i<3;i++){
        if(qs[0][y][i]-qs[0][x-1][i]!=qs[1][y][i]-qs[1][x-1][i])ch=1;
        cur[i]=qs[0][y][i]-qs[0][x-1][i];
    }if(ch)return -1;
    int rs=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)tt[i][j]=dp[y][i][j]-dp[x-1][i][j];
    cur[0]-=tt[0][0],cur[1]-=tt[1][1],cur[2]-=tt[2][2];
    rs+=min(tt[0][1],tt[1][0]),rs+=min(tt[0][2],tt[2][0]),rs+=min(tt[1][2],tt[2][1]);
    cur[0]-=min(tt[0][1],tt[1][0])+min(tt[0][2],tt[2][0]);
    rs+=2*cur[0];
    return rs;
}
/*int main(){
    init("ATACAT", "ACTATA");
    cout<<get_distance(1, 3);
}*/

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