Submission #642538

#	Time	Username	Problem	Language	Result	Execution time	Memory
642538		daisy2	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	8716 KiB

dna

#include "dna.h"
#include<iostream>
using namespace std;
int pr[100005][3][3],brl[2][100005][3];
void init(std::string a, std::string b) {

    int in1,in2;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='A') in1=0;
        else if(a[i]=='T') in1=1;
        else in1=2;

        if(b[i]=='A') in2=0;
        else if(b[i]=='T') in2=1;
        else in2=2;

        
        if(i!=0){
            for(int j1=0;j1<=2;j1++)
            {
                for(int j2=0;j2<=2;j2++)
                    pr[i][j1][j2]=pr[i-1][j1][j2];
            }
            for(int j1=0;j1<=1;j1++)
            {
                for(int j2=0;j2<=2;j2++)
                    brl[j1][i][j2]=brl[j1][i-1][j2];
            }
        }
        if(in1==in2) continue;

        pr[i][in1][in2]++;
        brl[0][i][in1]++;
        brl[1][i][in2]++;
    }
}

int get_distance(int x, int y) {

	int minim=0,minim2=0;
	for(int let=0;let<=2;let++)
    {
        if(x>0) {minim=brl[0][x-1][let];minim2=brl[1][x-1][let];}
        if(brl[0][y][let]-minim!=brl[1][y][let]-minim2)
            return -1;
    }
    int t01=pr[y][0][1],t10=pr[y][1][0],t02=pr[y][0][2],t20=pr[y][2][0],t12=pr[y][1][2],t21=pr[y][2][1];
    if(x>0) {t01-=pr[x-1][0][1];t10-=pr[x-1][1][0];t02-=pr[x-1][0][2];t20-=pr[x-1][2][0];t12-=pr[x-1][1][2];t21-=pr[x-1][2][1];}

	int m1=min(t01,t10);

	int m2=min(t02,t20);

	int m3=min(t12,t21),r;



	return m1+m2+m3+2*(max(t01,t10)-m1);
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:8:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i=0;i<a.size();i++)
      |                 ~^~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:55:22: warning: unused variable 'r' [-Wunused-variable]
   55 |  int m3=min(t12,t21),r;
      |                      ^

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