Submission #438924

#	Time	Username	Problem	Language	Result	Execution time	Memory
438924		DanerZein	DNA 돌연변이 (IOI21_dna)	C++17	71 / 100	1590 ms	5576 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];;
vector<int> da(3),dc(3),dt(3);
int n;
string u,v;
void init(std::string a, std::string b) {
  memset(na,0,sizeof na);
  memset(nb,0,sizeof nb);
  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]++;
  }
  u=a; v=b;
}

int get_distance(int x, int y) {
  for(int i=0;i<3;i++){
    da[i]=dc[i]=dt[i]=0;
  }
  int aa,ac,at,ba,bc,bt;
  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];
  }
  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];
  }
  if(aa!=ba || ac!=bc || at!=bt) return -1;
  
  int res=MAX;
  int rp,c,d=(y-x)+1;
  rp=c=0;
  for(int i=x;i<=y;i++){
    if(u[i]==v[i])continue;
    int id=0;
    if(u[i]=='A') id=0;
    if(u[i]=='C') id=1;
    if(u[i]=='T') id=2;
    
    if(v[i]=='A') da[id]++;
    if(v[i]=='C') dc[id]++;
    if(v[i]=='T') dt[id]++;
    c++;
  }
  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:45:7: warning: unused variable 'res' [-Wunused-variable]
   45 |   int res=MAX;
      |       ^~~
dna.cpp:46:12: warning: unused variable 'd' [-Wunused-variable]
   46 |   int rp,c,d=(y-x)+1;
      |            ^

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