Submission #444338

#	Time	Username	Problem	Language	Result	Execution time	Memory
444338		computerbox	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	6028 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;

int preff[100010][3][3];
int num[27];


void init(string a, string b) {
  num['A'-'A']=0;
  num['T'-'A']=1;
  num['C'-'A']=2;
  for(int i = 0; i < (int)a.size(); i++)
  {
    int x = num[a[i] - 'A'];	
    int y = num[b[i] - 'A'];
    preff[i][x][y]++;   
    if(i != 0)
    {
	  for(int x = 0; x < 3; x++)
	  {
		for(int y = 0; y < 3; y++)
		{
		  preff[i][x][y] += preff[i - 1][x][y];	
	    }  
	  }	
    }
  } 	
}

int get_distance(int x, int y) {
	int cnt[3][3];
	memset(cnt,0,sizeof(cnt));
	if(x == 0)
	{
	  for(int i = 0; i < 3; i++)
	  {
		for(int j = 0; j < 3; j++)
		{
		  cnt[i][j] += preff[y][i][j];	
	    }  
	  } 	
    }
    else
    {
	  for(int i = 0; i < 3; i++)
	  {
		for(int j = 0; j < 3; j++)
		{
		  cnt[i][j] += (preff[y][i][j] - preff[x - 1][i][j]);	
	    }  
	  } 	
    }
    
    int ans=0;
    for(int i = 0; i < 3; i++)
    {
	  for(int j = 0; j < 3; j++)
	  {
		if(i == j)continue;
		int cycle_2 = min(cnt[i][j],cnt[j][i]); 
		ans += cycle_2;
		cnt[i][j] -= cycle_2;
		cnt[j][i] -= cycle_2; 
	  }	
    }
    
    for(int i = 0; i < 3; i++)
    {
	  for(int j = 0; j < 3; j++)
	  {
		for(int k = 0; k < 3; k++)
		{
		  if(i == j || j == k || k == i)continue;
		  int cycle_3 = min(cnt[i][j],min(cnt[j][k],cnt[k][i]));
		  ans += cycle_3 * 2;	
		  cnt[i][j] -= cycle_3;
		  cnt[j][k] -= cycle_3;
		  cnt[k][i] -= cycle_3;
	    }  
	  }	
    }
    for(int i = 0; i < 3;i++)
    {
	  for(int j = 0; j < 3;j++)
	  {
		if(i == j)continue;
		if(cnt[i][j] > 0)return -1;  
	  } 	
    }   
	return ans;
}

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