Submission #454588

#	Time	Username	Problem	Language	Result	Execution time	Memory
454588		ogibogi2004	Mutating DNA (IOI21_dna)	C++17	100 / 100	83 ms	11052 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
int prcnt[MAXN][4][4];
int prcnt1[MAXN][4];
void init(string a, string b) {
	for(int i=1;i<=a.size();i++)
	{
		for(int j1=0;j1<4;j1++)
		{
			for(int j2=0;j2<4;j2++)
			{
				prcnt[i][j1][j2]=prcnt[i-1][j1][j2];
			}
			prcnt1[i][j1]=prcnt1[i-1][j1];
		}
		int c1=0,c2=0;
		if(a[i-1]=='A')c1=1;
		if(a[i-1]=='C')c1=2;
		if(a[i-1]=='T')c1=3;
		if(b[i-1]=='A')c2=1;
		if(b[i-1]=='C')c2=2;
		if(b[i-1]=='T')c2=3;
		prcnt[i][c1][c2]++;
		prcnt1[i][c1]++;
		prcnt1[i][c2]--;
	}
}

int get_distance(int x, int y) {
	x++;y++;
	int cnt[4][4];
	for(int j1=0;j1<4;j1++)
	{
		for(int j2=0;j2<4;j2++)
		{
			cnt[j1][j2]=prcnt[y][j1][j2]-prcnt[x-1][j1][j2];
		}
	}
	//cout<<"*\n";
	int cntswaps=0;
	for(int j=0;j<4;j++)
	{
		if(prcnt1[y][j]-prcnt1[x-1][j]!=0)return -1;
	}
	for(int j1=0;j1<4;j1++)
	{
		for(int j2=0;j2<4;j2++)
		{
			if(j1==j2)continue;
			cntswaps+=cnt[j1][j2];
		}
	}
	for(int j1=1;j1<4;j1++)
	{
		for(int j2=j1+1;j2<4;j2++)
		{
			int t=min(cnt[j1][j2],cnt[j2][j1]);
			cnt[j1][j2]-=t;cnt[j2][j1]-=t;
			cntswaps-=t;
		}
	}
	int cnt1=0;
	set<int>s;
	for(int j1=1;j1<4;j1++)
	{
		for(int j2=1;j2<4;j2++)
		{
			if(j1==j2)continue;
			if(cnt[j1][j2]>0)
			{
				s.insert(cnt[j1][j2]);
				cnt1++;
			}
		}
	}
	if(cnt1==0)return cntswaps;
	//cout<<s.size()<<endl;
	if(s.size()!=1)assert(false);
	return cntswaps-(*s.begin());
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:8:15: 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=1;i<=a.size();i++)
      |              ~^~~~~~~~~~

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