Submission #598665

#	Time	Username	Problem	Language	Result	Execution time	Memory
598665		MKopchev	Mutating DNA (IOI21_dna)	C++17	100 / 100	88 ms	7432 KiB

dna

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

const int nmax=1e6+42;

int pref[nmax][3][3];

int id(char c)
{
    if(c=='A')return 0;
    if(c=='T')return 1;
    return 2;
}

void init(std::string a, std::string b)
{
    int n=a.size();

    for(int i=0;i<n;i++)
    {
        if(i)
        {
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++)
                    pref[i][j][k]=pref[i-1][j][k];
        }

        pref[i][id(a[i])][id(b[i])]++;
    }

}

int cur[3][3];

int sum(vector<int> order)
{
    order.push_back(order[0]);

    int mini=1e9;

    for(int i=1;i<order.size();i++)
        mini=min(mini,cur[order[i-1]][order[i]]);

    //cout<<mini<<" -> ";for(auto w:order)cout<<w<<" ";cout<<endl;

    for(int i=1;i<order.size();i++)
        cur[order[i-1]][order[i]]-=mini;

    return mini*(order.size()-2);
}

int get_distance(int x, int y)
{
    for(int j=0;j<3;j++)
        for(int k=0;k<3;k++)
        {
            cur[j][k]=pref[y][j][k];

            if(x)cur[j][k]-=pref[x-1][j][k];
        }

    cur[0][0]=0;
    cur[1][1]=0;
    cur[2][2]=0;

    /*
    for(int j=0;j<3;j++)
    {
        for(int k=0;k<3;k++)cout<<cur[j][k]<<" ";
        cout<<endl;
    }
    */

    int output=0;

    output+=sum({0,1});
    output+=sum({0,2});
    output+=sum({1,2});

    output+=sum({0,1,2});
    output+=sum({0,2,1});

    for(int j=0;j<3;j++)
        for(int k=0;k<3;k++)
            if(cur[j][k])return -1;

    return output;
}

/*
int main() {
	int n, q;
	assert(scanf("%d %d", &n, &q) == 2);
	char A[n+1], B[n+1];
	assert(scanf("%s", A) == 1);
	assert(scanf("%s", B) == 1);
	std::string a = std::string(A);
	std::string b = std::string(B);
	std::vector<int> x(q), y(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);
	std::vector<int> results(q);
	init(a, b);
	for (int i = 0; i < q; i++) {
		results[i] = get_distance(x[i], y[i]);
	}
	for (int i = 0; i < q; i++) {
		printf("%d\n", results[i]);
	}
	fclose(stdout);
	return 0;
}
*/

Compilation message (stderr)

dna.cpp: In function 'int sum(std::vector<int>)':
dna.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=1;i<order.size();i++)
      |                 ~^~~~~~~~~~~~~
dna.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=1;i<order.size();i++)
      |                 ~^~~~~~~~~~~~~

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