Submission #722200

#	Time	Username	Problem	Language	Result	Execution time	Memory
722200		Yell0	Mutating DNA (IOI21_dna)	C++17	100 / 100	57 ms	10108 KiB

dna

#include <bits/stdc++.h>
 
using namespace std;
const int MN=1e5+2;
int N,pfa[2][MN],pfc[2][MN],pft[2][MN],pfsw[3][3][MN];
string S[2];

void init(string a,string b) {
  N=a.size();
  S[0]=a,S[1]=b;
  for(int i=1;i<=N;++i)
    for(int j=0;j<2;++j) {
      pfa[j][i]=pfa[j][i-1]+(S[j][i-1]=='A');
      pfc[j][i]=pfc[j][i-1]+(S[j][i-1]=='C');
      pft[j][i]=pft[j][i-1]+(S[j][i-1]=='T');
    }
  for(int i=1;i<=N;++i) {
    char xc=S[0][i-1],yc=S[1][i-1];
    int x=(xc=='A'?0:(xc=='C'?1:2)),y=(yc=='A'?0:(yc=='C'?1:2));
    for(int k=0;k<3;++k) for(int l=0;l<3;++l) pfsw[k][l][i]=pfsw[k][l][i-1]+(k==x&&l==y);
  }
}

int get_distance(int x,int y) {
  ++x,++y;
  if(pfa[0][y]-pfa[0][x-1]!=pfa[1][y]-pfa[1][x-1]||pfc[0][y]-pfc[0][x-1]!=pfc[1][y]-pfc[1][x-1]||pft[0][y]-pft[0][x-1]!=pft[1][y]-pft[1][x-1]) return -1;
  int ans=0,sw[3][3],tsw=0;
  for(int k=0;k<3;++k) for(int l=0;l<3;++l) {
    if(k==l) continue;
    sw[k][l]=pfsw[k][l][y]-pfsw[k][l][x-1];
    tsw+=sw[k][l];
  }
  for(int k=0;k<3;++k) for(int l=k+1;l<3;++l) {
    ans+=min(sw[k][l],sw[l][k]);
    tsw-=min(sw[k][l],sw[l][k])*2;
  }
  ans+=tsw*2/3;
  return ans;
}

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