Submission #696664

#	Time	Username	Problem	Language	Result	Execution time	Memory
696664		sharaelong	Mutating DNA (IOI21_dna)	C++17	100 / 100	43 ms	9752 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 1e5 + 1;

int psa[MAX_N][3];
int psb[MAX_N][3];
int ps[MAX_N][3][3];

void init(string a, string b) {
    for (int i=0; i<a.size(); ++i) {
        if (a[i] == 'A') a[i] = 0;
        else if (a[i] == 'T') a[i] = 1;
        else a[i] = 2;
        if (b[i] == 'A') b[i] = 0;
        else if (b[i] == 'T') b[i] = 1;
        else b[i] = 2;
    }
    for (int i=0; i<a.size(); ++i) {
        for (int j=0; j<3; ++j) {
            psa[i+1][j] = psa[i][j] + (a[i] == j);
            psb[i+1][j] = psb[i][j] + (b[i] == j);
        }
    }
    for (int i=0; i<a.size(); ++i) {
        for (int j=0; j<3; ++j) {
            for (int k=0; k<3; ++k) {
                ps[i+1][j][k] = ps[i][j][k] + (a[i] == j && b[i] == k);
            }
        }
    }
}

int get_distance(int x, int y) {
	x++; y++;
    for (int i=0; i<3; ++i) {
        if (psa[y][i]-psa[x-1][i] != psb[y][i]-psb[x-1][i]) {
            return -1;
        }
    }

    int a = ps[y][0][1]-ps[x-1][0][1];
    int b = ps[y][1][0]-ps[x-1][1][0];
    int c = ps[y][0][2]-ps[x-1][0][2];
    int d = ps[y][2][0]-ps[x-1][2][0];
    int e = ps[y][1][2]-ps[x-1][1][2];
    int f = ps[y][2][1]-ps[x-1][2][1];
    return min(a,b)+min(c,d)+min(e,f)+2*abs(a-b);
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i=0; i<a.size(); ++i) {
      |                   ~^~~~~~~~~
dna.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0; i<a.size(); ++i) {
      |                   ~^~~~~~~~~
dna.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i=0; i<a.size(); ++i) {
      |                   ~^~~~~~~~~

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