Submission #1015928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015928		deera	Mutating DNA (IOI21_dna)	C++17	56 / 100	700 ms	7084 KiB

dna

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

#include "dna.h"

string A, B;

map<char, vector<int>> A_counts;
map<char, vector<int>> B_counts;
vector<int> diffs;

void init(string a, string b) {
    A = a;
    B = b;

    A_counts['A'].push_back(0);
    A_counts['C'].push_back(0);
    A_counts['T'].push_back(0);

    B_counts['A'].push_back(0);
    B_counts['C'].push_back(0);
    B_counts['T'].push_back(0);

    diffs.push_back(0);

    if (a[0] == 'A') { A_counts['A'].push_back(1); } else { A_counts['A'].push_back(0); }
    if (a[0] == 'C') { A_counts['C'].push_back(1); } else { A_counts['C'].push_back(0); }
    if (a[0] == 'T') { A_counts['T'].push_back(1); } else { A_counts['T'].push_back(0); }

    if (b[0] == 'A') { B_counts['A'].push_back(1); } else { B_counts['A'].push_back(0); }
    if (b[0] == 'C') { B_counts['C'].push_back(1); } else { B_counts['C'].push_back(0); }
    if (b[0] == 'T') { B_counts['T'].push_back(1); } else { B_counts['T'].push_back(0); }

    if (a[0] != b[0]) {
        diffs.push_back(1);
    } else {
        diffs.push_back(0);
    }

    for (int i=1; i<a.size();i++) {
        A_counts['A'].push_back(A_counts['A'][i] + (a[i] == 'A'));
        A_counts['C'].push_back(A_counts['C'][i] + (a[i] == 'C'));
        A_counts['T'].push_back(A_counts['T'][i] + (a[i] == 'T'));

        B_counts['A'].push_back(B_counts['A'][i] + (b[i] == 'A'));
        B_counts['C'].push_back(B_counts['C'][i] + (b[i] == 'C'));
        B_counts['T'].push_back(B_counts['T'][i] + (b[i] == 'T'));

        if (a[i] != b[i]) {
            diffs.push_back(diffs[i] + 1);
        } else {
            diffs.push_back(diffs[i]);
        }
    }

}

int get_distance(int x, int y) {
    string a = A.substr(x, (y-x+1));
    string b = B.substr(x, (y-x+1));


    if (a == b)
        return 0;


    int n = y - x + 1;
    y++;

    if (n == 1)
        return -1;

    if (A_counts['A'][y] - A_counts['A'][x] != B_counts['A'][y] - B_counts['A'][x] ||
        A_counts['C'][y] - A_counts['C'][x] != B_counts['C'][y] - B_counts['C'][x] ||
        A_counts['T'][y] - A_counts['T'][x] != B_counts['T'][y] - B_counts['T'][x]) {
        return -1;
    }

    n = diffs[y] - diffs[x];

    if (n == 0)
        return 0;

    if (n == 2 || n == 3)
        return n - 1;

    return (n / 2) + (n % 2);
    
}

Compilation message (stderr)

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

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