Submission #1053264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053264		Zicrus	Mutating DNA (IOI21_dna)	C++17	100 / 100	38 ms	11608 KiB

dna

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

typedef long long ll;

string a, b;
vector<ll> sum, sumA, sumB, sumAC, sumBC;
vector<ll> sumAonC, sumAonT, sumConA, sumConT, sumTonA, sumTonC;

void init(string a1, string b1) {
    a = a1; b = b1;
    sum = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sum[i] = sum[i-1] + (a[i-1] != b[i-1]);
    }
    sumA = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumA[i] = sumA[i-1] + (a[i-1] == 'A');
    }
    sumB = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumB[i] = sumB[i-1] + (b[i-1] == 'A');
    }
    sumAC = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumAC[i] = sumAC[i-1] + (a[i-1] == 'C');
    }
    sumBC = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumBC[i] = sumBC[i-1] + (b[i-1] == 'C');
    }
    //
    sumAonC = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumAonC[i] = sumAonC[i-1] + (a[i-1] == 'A' && b[i-1] == 'C');
    }
    sumAonT = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumAonT[i] = sumAonT[i-1] + (a[i-1] == 'A' && b[i-1] == 'T');
    }
    sumConA = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumConA[i] = sumConA[i-1] + (a[i-1] == 'C' && b[i-1] == 'A');
    }
    sumConT = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumConT[i] = sumConT[i-1] + (a[i-1] == 'C' && b[i-1] == 'T');
    }
    sumTonA = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumTonA[i] = sumTonA[i-1] + (a[i-1] == 'T' && b[i-1] == 'A');
    }
    sumTonC = vector<ll>(a.size()+1);
    for (int i = 1; i <= a.size(); i++) {
        sumTonC[i] = sumTonC[i-1] + (a[i-1] == 'T' && b[i-1] == 'C');
    }
}

int get_distance(int x, int y) {
    if (sumA[y+1] - sumA[x] != sumB[y+1] - sumB[x] ||
        sumAC[y+1] - sumAC[x] != sumBC[y+1] - sumBC[x]) return -1;
        
    ll AonC = sumAonC[y+1] - sumAonC[x];
    ll AonT = sumAonT[y+1] - sumAonT[x];
    ll ConA = sumConA[y+1] - sumConA[x];
    ll ConT = sumConT[y+1] - sumConT[x];
    ll TonA = sumTonA[y+1] - sumTonA[x];
    ll TonC = sumTonC[y+1] - sumTonC[x];
    ll ac = min(AonC, ConA);
    ll tc = min(TonC, ConT);
    ll at = min(AonT, TonA);
    ll res = ac + tc + at;
    AonC -= ac;
    AonT -= at;
    ConA -= ac;
    ConT -= tc;
    TonA -= at;
    TonC -= tc;
    ac = max(AonC, ConA);
    tc = max(TonC, ConT);
    at = max(AonT, TonA);
    vector<ll> g = {ac, tc, at};
    sort(g.begin(), g.end());
    res += g[0] + g[1];
    return res;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:14:23: 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 = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:18:23: 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 <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:22:23: 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 = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~
dna.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 1; i <= a.size(); i++) {
      |                     ~~^~~~~~~~~~~

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