Submission #789730

#	Time	Username	Problem	Language	Result	Execution time	Memory
789730		Liudas	Mutating DNA (IOI21_dna)	C++17	100 / 100	323 ms	58516 KiB

dna

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
string s, s1;
vector<int> dif;
vector<array<int, 3>> need, got;
vector<map<string, int>> seq;
void init(string a, string b){
    s = a;
    s1 = b;
    dif.assign(s.size(), 0);
    need.assign(s.size(), {0,0,0});
    got.assign(s.size(), {0,0,0});
    map<char, int> _map = {{'A',0},{'C',1},{'T',2}};
    map<string, int> map2 = {{"AT",0},{"TA", 0},{"AC",0},{"CA",0},{"CT",0},{"TC", 0}};
    vector<int> n1(3,0), n2(3,0);
    seq.resize(s.size());
    int t = 0, diff = 0;
    for(int i = 0; i < s.size(); i ++){
        string lo = string(1, s1[i]), ol = string(1, s[i]);
        string lol = lo + ol;
        if(s1[i] != s[i]){
            map2[lol]++;
            n1[_map[s[i]]]++;
            n2[_map[s1[i]]]++;
            diff++;
        }
        for(auto[l,r]:map2){
            seq[i][l] = r;
        }
        for(int j = 0; j < 3; j ++){
            need[i][j] = n1[j];
            got[i][j] = n2[j];
        }
        dif[i] = diff;
    }
}
int get_distance(int x, int y){
    int score = 0;
    array<int, 3> d1, d2;
    map<string, int> retard;
    for(int i = 0; i < 3; i ++){
        d1[i] = need[y][i] - (x > 0 ? need[x-1][i] : 0);
        d2[i] = got[y][i] - (x > 0 ? got[x-1][i] : 0);
    }
    for(auto [l,r] : seq[y]){
        int a = r - (x > 0 ? seq[x-1][l] : 0);
        retard[l] = a;
    }
    int irl = 0;
    for(auto [l, r] : retard){
        int t = min(r, retard[string(1,l[1]) + string(1,l[0])]);
        retard[l] -= t;
        retard[string(1,l[1]) + string(1,l[0])] -= t;
        score += t;
        irl += retard[l];
    }
    if(d1 != d2){
        return -1;
    }
    else{
        return score + irl * 2 / 3;
    }
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:19:22: 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 = 0; i < s.size(); i ++){
      |                    ~~^~~~~~~~~~
dna.cpp:18:9: warning: unused variable 't' [-Wunused-variable]
   18 |     int t = 0, diff = 0;
      |         ^

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