Submission #642535

#	Time	Username	Problem	Language	Result	Execution time	Memory
642535		daisy2	Mutating DNA (IOI21_dna)	C++17	0 / 100	36 ms	8204 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(in1==in2) continue;

        if(i!=0){
            for(int j1=0;j1<=3;j1++)
            {
                for(int j2=0;j2<=3;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];
            }
        }
        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);
	t01-=m1;t10-=m1;

	int m2=min(t02,t20);
	t02-=m2;t20-=m2;

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

	if(t01!=0) r=t01*2;
	else r=t10*2;

	return r+m1+m2+m3;
}

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:24:49: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
   24 |                     pr[i][j1][j2]=pr[i-1][j1][j2];
      |                                   ~~~~~~~~~~~~~~^
dna.cpp:23:32: note: within this loop
   23 |                 for(int j2=0;j2<=3;j2++)
      |                              ~~^~~

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