Submission #438928

#	Time	Username	Problem	Language	Result	Execution time	Memory
438928		DanerZein	Mutating DNA (IOI21_dna)	C++17	100 / 100	64 ms	12056 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX=1e9;
const int MAX_N=1e5+10;
int na[MAX_N][4],nb[MAX_N][4];
int gda[MAX_N][4],gdc[MAX_N][4],gdt[MAX_N][4];
int dif[MAX_N];
vector<int> da(3),dc(3),dt(3);
int n;
void init(std::string a, std::string b) {
  memset(na,0,sizeof na);
  memset(nb,0,sizeof nb);
  memset(gda,0,sizeof gda); memset(gdc,0,sizeof gdc); memset(gdt,0,sizeof gdt);
  memset(dif,0,sizeof dif);
  n=a.size();
  for(int i=0;i<n;i++){
    if(i!=0){
      for(int j=0;j<3;j++) na[i][j]=na[i-1][j];
      for(int j=0;j<3;j++) nb[i][j]=nb[i-1][j];
    }
    if(a[i]=='A') na[i][0]++;
    if(a[i]=='C') na[i][1]++;
    if(a[i]=='T') na[i][2]++;
    
    if(b[i]=='A') nb[i][0]++;
    if(b[i]=='C') nb[i][1]++;
    if(b[i]=='T') nb[i][2]++;
  }
  for(int i=0;i<n;i++){
    if(i!=0){
      dif[i]=dif[i-1];
      for(int j=0;j<3;j++) gda[i][j]=gda[i-1][j];
      for(int j=0;j<3;j++) gdc[i][j]=gdc[i-1][j];
      for(int j=0;j<3;j++) gdt[i][j]=gdt[i-1][j];
    }
    if(a[i]!=b[i]) dif[i]++;
    int id=0;
    if(a[i]=='A') id=0;
    if(a[i]=='C') id=1;
    if(a[i]=='T') id=2;
    
    if(b[i]=='A') gda[i][id]++;
    if(b[i]=='C') gdc[i][id]++;
    if(b[i]=='T') gdt[i][id]++;
  }
}

int get_distance(int x, int y) {
  int aa,ac,at,ba,bc,bt,c;
  if(x==0){
    aa=na[y][0]; ac=na[y][1]; at=na[y][2];
    ba=nb[y][0]; bc=nb[y][1]; bt=nb[y][2];
    da[0]=gda[y][0]; da[1]=gda[y][1]; da[2]=gda[y][2];
    dc[0]=gdc[y][0]; dc[1]=gdc[y][1]; dc[2]=gdc[y][2];
    dt[0]=gdt[y][0]; dt[1]=gdt[y][1]; dt[2]=gdt[y][2];
    c=dif[y];
  }
  else{
    aa=na[y][0]-na[x-1][0]; ac=na[y][1]-na[x-1][1]; at=na[y][2]-na[x-1][2];
    ba=nb[y][0]-nb[x-1][0]; bc=nb[y][1]-nb[x-1][1]; bt=nb[y][2]-nb[x-1][2];
    da[0]=gda[y][0]-gda[x-1][0]; da[1]=gda[y][1]-gda[x-1][1]; da[2]=gda[y][2]-gda[x-1][2];
    dc[0]=gdc[y][0]-gdc[x-1][0]; dc[1]=gdc[y][1]-gdc[x-1][1]; dc[2]=gdc[y][2]-gdc[x-1][2];
    dt[0]=gdt[y][0]-gdt[x-1][0]; dt[1]=gdt[y][1]-gdt[x-1][1]; dt[2]=gdt[y][2]-gdt[x-1][2];
    c=dif[y]-dif[x-1];
  }
  if(aa!=ba || ac!=bc || at!=bt) return -1;
  
  int res=MAX;
  int rp,d=(y-x)+1;
  rp=0;
  for(int i=0;i<3;i++){
    if(dc[i]==0) continue;
    int mi;
    if(i==0){
      mi=min(dc[i],da[1]);
      dc[i]-=mi; da[1]-=mi;
      rp+=mi; c-=mi*2;
    }
    if(i==2){
      mi=min(dc[i],dt[1]);
      dc[i]-=mi; dt[1]-=mi;
      rp+=mi; c-=mi*2;
    }
  }
  for(int i=0;i<3;i++){
    if(dc[i]==0) continue;
    if(i==0){
      rp+=dc[i]; c-=dc[i]; 
      dt[0]+=dc[i];
      dc[i]=0;
    }
    if(i==2){
      rp+=dc[i]; c-=dc[i];
      da[2]+=dc[i];
      dc[i]=0;
    }
  }
  rp+=c/2;
  return rp;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:69:7: warning: unused variable 'res' [-Wunused-variable]
   69 |   int res=MAX;
      |       ^~~
dna.cpp:70:10: warning: unused variable 'd' [-Wunused-variable]
   70 |   int rp,d=(y-x)+1;
      |          ^

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