Submission #1195157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195157		DobromirAngelov	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	28 ms	10400 KiB

dna

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

using namespace std;

const int MAXN=1e5+5;

int n;
int a[MAXN];
int b[MAXN];
int pref1[MAXN][4];
int pref2[MAXN][4];
int pref[MAXN][10];

int cd(int x,int y)
{
    if(x==1 && y==2) return 1;
    if(x==2 && y==1) return 2;
    if(x==3 && y==1) return 3;
    if(x==1 && y==3) return 4;
    if(x==2 && y==3) return 5;
    if(x==3 && y==2) return 6;
    return 0;
}

void init(std::string s1, std::string s2)
{
	n=s1.size();
	s1='$'+s1;
    s2='$'+s2;

    for(int i=1;i<=n;i++)
    {
        if(s1[i]=='A') a[i]=1;
        if(s1[i]=='C') a[i]=2;
        if(s1[i]=='T') a[i]=3;
    }
    for(int i=1;i<=n;i++)
    {
        if(s2[i]=='A') b[i]=1;
        if(s2[i]=='C') b[i]=2;
        if(s2[i]=='T') b[i]=3;
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=3;j++) pref1[i][j]=pref1[i-1][j];
        for(int j=1;j<=3;j++) pref2[i][j]=pref2[i-1][j];
        pref1[i][a[i]]++;
        pref2[i][b[i]]++;
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=6;j++) pref[i][j]=pref[i-1][j];
        pref[i][cd(a[i],b[i])]++;
    }
}

int get_distance(int l, int r)
{
	l++; r++;

	bool fl=0;
	for(int j=1;j<=3;j++)
		if(pref1[r][j]-pref1[l-1][j]!=pref2[r][j]-pref2[l-1][j]) fl=1;
	if(fl) return -1;

	int ans=0;
	int s=0;
	for(int j=1;j<=3;j++)
	{
		int x=pref[r][2*j-1]-pref[l-1][2*j-1];
		int y=pref[r][2*j]-pref[l-1][2*j];
		ans+=min(x,y);
		s+=max(x,y)-min(x,y);
	}
	ans+=2*(s/3);
	return ans;
}

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