Submission #1045721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045721		Unforgettablepl	Mutating DNA (IOI21_dna)	C++17	100 / 100	72 ms	23416 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<vector<int>>> prefs;

void init(string a,string b){
	int n = a.size();
	a.insert(a.begin(),'$');
	b.insert(b.begin(),'$');
	prefs = vector(n+1,vector(3,vector(3,0)));
	for(int i=1;i<=n;i++){
		int curra;
		if(a[i]=='A')curra=0;
		else if(a[i]=='C')curra=1;
		else if(a[i]=='T')curra=2;
		int currb;
		if(b[i]=='A')currb=0;
		else if(b[i]=='C')currb=1;
		else if(b[i]=='T')currb=2;
		prefs[i]=prefs[i-1];
		prefs[i][currb][curra]++;
	}
}

int get_distance(int x, int y) {
	y++;
	auto curr = prefs[y];
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)curr[i][j]-=prefs[x][i][j];
	int ans = 0;
	for(int i=0;i<3;i++){
		curr[i][i]=0;
		for(int j=i+1;j<3;j++){
			int co = min(curr[i][j],curr[j][i]);
			ans+=co;
			curr[i][j]-=co;
			curr[j][i]-=co;
		}
	}
	int direction = -1;
	if(curr[0][1]>=curr[1][0] and curr[1][2]>=curr[2][1] and curr[2][0]>=curr[0][2] and curr[0][1]==curr[1][2] and curr[1][2]==curr[2][0]){
		return ans+curr[0][1]+curr[1][2];
	}
	if(curr[0][1]<=curr[1][0] and curr[1][2]<=curr[2][1] and curr[2][0]<=curr[0][2] and curr[0][2]==curr[2][1] and curr[2][1]==curr[1][0]){
		return ans+curr[1][0]+curr[2][1];
	}
	return -1;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:40:6: warning: unused variable 'direction' [-Wunused-variable]
   40 |  int direction = -1;
      |      ^~~~~~~~~
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:22:17: warning: 'currb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |   prefs[i][currb][curra]++;
      |                 ^
dna.cpp:22:24: warning: 'curra' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |   prefs[i][currb][curra]++;
      |                        ^

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