Submission #858244

#	Time	Username	Problem	Language	Result	Execution time	Memory
858244		lentibear	Mutating DNA (IOI21_dna)	C++17	100 / 100	32 ms	6284 KiB

dna

#include <string>
#include <vector>
using namespace std;

void init(std::string a, std::string b);
int get_distance(int x, int y);

vector<int> ct[6];
void init(std::string a, std::string b){
	int n=min(a.size(),b.size());
	for(int j=0; j<6; j++) ct[j]= vector<int> (n);
	for(int i=0; i<n; i++) {
       if(i>0) for(int j=0; j<6; j++) ct[j][i]=ct[j][i-1];
       else for(int j=0; j<6; j++) ct[j][i]=0;
       if(a[i]=='A'){
           if(b[i]=='T') ct[0][i]++;
           else if (b[i]=='C') ct[1][i]++;
       }
       if(a[i]=='T'){
           if(b[i]=='A') ct[2][i]++;
           else if (b[i]=='C') ct[3][i]++;
       }
       if(a[i]=='C'){
           if(b[i]=='A') ct[4][i]++;
           else if (b[i]=='T') ct[5][i]++;
       }
    }
}

int get_distance(int x, int y){
	int nct[6];
    for(int j=0; j<6; j++) nct[j]=ct[j][y];
    if(x>0)  for(int j=0; j<6; j++) nct[j]-=ct[j][x-1];
    if(nct[0]+nct[1]==nct[2]+nct[4] && nct[2]+nct[3]==nct[0]+nct[5]){
      return(min(nct[0], nct[2])+min(nct[1],nct[4])+min(nct[3],nct[5])+max(nct[0]-nct[2],0)*2+max(nct[1]-nct[4],0)*2);
    }
    return(-1);
}

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