제출 #1241374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241374		Younis_Dwai	DNA 돌연변이 (IOI21_dna)	C++20	71 / 100	1594 ms	6152 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
#define in insert
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,B[N],C[N],pref[2][N][4],d[N][2];
void init(std::string a, std::string b){
     n=a.size();
     for(int i=1;i<=n;i++){
            if(a[i-1]=='A') B[i]=1;
            else if(a[i-1]=='T') B[i]=2;
            else B[i]=3;
     }
     for(int i=1;i<=n;i++){
            if(b[i-1]=='A') C[i]=1;
            else if(b[i-1]=='T') C[i]=2;
            else C[i]=3;
     }
     for(int i=1;i<=n;i++){
         for(int j=1;j<=3;j++){
             pref[0][i][j]=pref[0][i-1][j]+bool(B[i]==j);
             pref[1][i][j]=pref[1][i-1][j]+bool(C[i]==j);
         }
     }
     return ;
}

int get_distance(int x, int y){
    ++x;++y;
    bool can=1;
    for(int j=1;j<=3;j++){
        if(pref[0][y][j]-pref[0][x-1][j]!=pref[1][y][j]-pref[1][x-1][j]) can=0;
    }
    if(!can) return -1;
    int ret=0;
    int cnt[4][4];
    memset(cnt,0,sizeof cnt);
    for(int i=x;i<=y;i++){
        if(B[i]==C[i]) continue ;

           cnt[B[i]][C[i]]++;
    }
    for(int i=1;i<=3;i++){
        for(int j=i+1;j<=3;j++){
            int most=min(cnt[i][j],cnt[j][i]);
            cnt[i][j]-=most;
            cnt[j][i]-=most;
            ret+=most;
        }
    }
    //cout<<" # "<<ret<<' '<<endl;
    int sum=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            if(i==j) continue ;
            sum+=cnt[i][j];
        }
    }
    ret+=(sum/3)*2;
	return ret;
}

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