제출 #542835

#제출 시각아이디문제언어결과실행 시간메모리
542835alexdumitruDNA 돌연변이 (IOI21_dna)C++17
56 / 100
58 ms8932 KiB
#include <bits/stdc++.h> using namespace std; int sa1[100005],st1[100005],sc1[100005],sa2[100005],st2[100005],sc2[100005]; int pepoz[100005]; int AT[100005]; int AC[100005]; int CA[100005]; int CT[100005]; int TA[100005]; int TC[100005]; int i,n; int geta1(int i, int j) { if(!i)return sa1[j]; return sa1[j]-sa1[i-1]; } int gett1(int i, int j) { if(!i)return st1[j]; return st1[j]-st1[i-1]; } int getc1(int i, int j) { if(!i)return sc1[j]; return sc1[j]-sc1[i-1]; } int geta2(int i, int j) { if(!i)return sa2[j]; return sa2[j]-sa2[i-1]; } int getat(int i, int j) { if(!i)return AT[j]; return AT[j]-AT[i-1]; } int getac(int i, int j) { if(!i)return AC[j]; return AC[j]-AC[i-1]; } int getca(int i, int j) { if(!i)return CA[j]; return CA[j]-CA[i-1]; } int getct(int i, int j) { if(!i)return CT[j]; return CT[j]-CT[i-1]; } int getta(int i, int j) { if(!i)return TA[j]; return TA[j]-TA[i-1]; } int gettc(int i, int j) { if(!i)return TC[j]; return TC[j]-TC[i-1]; } int cate(int i, int j) { if(!i)return pepoz[j]; return pepoz[j]-pepoz[i-1]; } int gett2(int i, int j) { if(!i)return st2[j]; return st2[j]-st2[i-1]; } int getc2(int i, int j) { if(!i)return sc2[j]; return sc2[j]-sc2[i-1]; } bool samea(int i, int j) { return geta1(i,j)==geta2(i,j); } bool samet(int i, int j) { return gett1(i,j)==gett2(i,j); } bool samec(int i, int j) { return getc1(i,j)==getc2(i,j); } void init(string a, string b) { n=a.length(); sa1[0]=(a[0]=='A'); st1[0]=(a[0]=='T'); sc1[0]=(a[0]=='C'); for(i=1;i<n;i++) { sa1[i]=sa1[i-1]; st1[i]=st1[i-1]; sc1[i]=sc1[i-1]; if(a[i]=='A')sa1[i]++; else if(a[i]=='T')st1[i]++; else sc1[i]++; } sa2[0]=(b[0]=='A'); st2[0]=(b[0]=='T'); sc2[0]=(b[0]=='C'); pepoz[0]=(a[0]==b[0]); i=0; if(a[i]=='A') { if(b[i]=='T')AT[i]++; else if(b[i]=='C')AC[i]++; } if(a[i]=='C') { if(b[i]=='A')CA[i]++; else if(b[i]=='T')CT[i]++; } if(a[i]=='T') { if(b[i]=='A')TA[i]++; else if(b[i]=='C')TC[i]++; } for(i=1;i<n;i++) { sa2[i]=sa2[i-1]; st2[i]=st2[i-1]; sc2[i]=sc2[i-1]; if(b[i]=='A')sa2[i]++; else if(b[i]=='T')st2[i]++; else sc2[i]++; pepoz[i]=pepoz[i-1]+(a[i]==b[i]); AT[i]=AT[i-1]; AC[i]=AC[i-1]; CA[i]=CA[i-1]; CT[i]=CT[i-1]; TA[i]=TA[i-1]; TC[i]=TC[i-1]; if(a[i]=='A') { if(b[i]=='T')AT[i]++; else if(b[i]=='C')AC[i]++; } if(a[i]=='C') { if(b[i]=='A')CA[i]++; else if(b[i]=='T')CT[i]++; } if(a[i]=='T') { if(b[i]=='A')TA[i]++; else if(b[i]=='C')TC[i]++; } } } int get_distance(int x, int y) { if(!samea(x,y)||!samet(x,y)||!samec(x,y))return -1; int ans=y-x+1; int swps=0; ans-=cate(x,y); swps+=min(getat(x,y),getta(x,y)); swps+=min(getac(x,y),getca(x,y)); swps+=min(getct(x,y),gettc(x,y)); int rezolvate=swps*2; int maitrebuie=ans-rezolvate; return max(0,maitrebuie-1)+swps; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...