Submission #844392

#	Time	Username	Problem	Language	Result	Execution time	Memory
844392		12345678	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	10320 KiB

dna

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

using namespace std;

const int nx=1e5+5;
int A[nx][3], B[nx][3], mp[128], ms[nx][3][3], s[3][3];
string sa, sb;

int d(int v1, int v2)
{
    return min(v1, v2);
}

void init(std::string a, std::string b) {
	mp['A']=0; mp['T']=1; mp['C']=2;
	for (int i=1; i<=a.size(); i++) A[i][0]=A[i-1][0], A[i][1]=A[i-1][1], A[i][2]=A[i-1][2], A[i][mp[a[i-1]]]++;
	for (int i=1; i<=b.size(); i++) B[i][0]=B[i-1][0], B[i][1]=B[i-1][1], B[i][2]=B[i-1][2], B[i][mp[b[i-1]]]++;
	for (int i=1; i<=a.size(); i++)
    {
        for (int j=0; j<3; j++) for (int k=0; k<3; k++) ms[i][j][k]=ms[i-1][j][k];
        if (a[i-1]!=b[i-1]) ms[i][mp[a[i-1]]][mp[b[i-1]]]++;
    }
	sa=a; sb=b;
}

int get_distance(int x, int y) {
	x++; y++;
    int cnt=0, ans=0;
	bool can=1;
	for (int i=0; i<3; i++) if (A[y][i]-A[x-1][i]!=B[y][i]-B[x-1][i]) can=0;
	if (!can) return -1;
	for (int i=0; i<3; i++) for (int j=0; j<3; j++) cnt+=ms[y][i][j]-ms[x-1][i][j], s[i][j]=ms[y][i][j]-ms[x-1][i][j];
    /*
    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++) cout<<s[i][j]<<' ';
        cout<<'\n';
    }*/
    int vl=d(s[1][0], s[0][1]);
    ans+=vl;
    cnt-=2*vl;
    vl=d(s[1][2], s[2][1]);
    ans+=vl;
    cnt-=2*vl;
    vl=d(s[0][2], s[2][0]);
    ans+=vl;
    cnt-=2*vl;
    return ans+2*cnt/3;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int i=1; i<=a.size(); i++) A[i][0]=A[i-1][0], A[i][1]=A[i-1][1], A[i][2]=A[i-1][2], A[i][mp[a[i-1]]]++;
      |                ~^~~~~~~~~~
dna.cpp:17:105: warning: array subscript has type 'char' [-Wchar-subscripts]
   17 |  for (int i=1; i<=a.size(); i++) A[i][0]=A[i-1][0], A[i][1]=A[i-1][1], A[i][2]=A[i-1][2], A[i][mp[a[i-1]]]++;
      |                                                                                                         ^
dna.cpp:18:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i=1; i<=b.size(); i++) B[i][0]=B[i-1][0], B[i][1]=B[i-1][1], B[i][2]=B[i-1][2], B[i][mp[b[i-1]]]++;
      |                ~^~~~~~~~~~
dna.cpp:18:105: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |  for (int i=1; i<=b.size(); i++) B[i][0]=B[i-1][0], B[i][1]=B[i-1][1], B[i][2]=B[i-1][2], B[i][mp[b[i-1]]]++;
      |                                                                                                         ^
dna.cpp:19:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for (int i=1; i<=a.size(); i++)
      |                ~^~~~~~~~~~
dna.cpp:22:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |         if (a[i-1]!=b[i-1]) ms[i][mp[a[i-1]]][mp[b[i-1]]]++;
      |                                            ^
dna.cpp:22:56: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |         if (a[i-1]!=b[i-1]) ms[i][mp[a[i-1]]][mp[b[i-1]]]++;
      |                                                        ^

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