Submission #1083537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083537		Roumak77	Mutating DNA (IOI21_dna)	C++17	100 / 100	48 ms	20680 KiB

dna

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

string a, b;
vector<vector<int>> cnts1(100001, vector<int>{0, 0, 0}); // a, t, c
vector<vector<int>> cnts2(100001, vector<int>{0, 0, 0});
vector<vector<int>> list_n(100001, vector<int>{0, 0, 0, 0, 0, 0}); //at, ta, ac, ca, tc, ct




void init(string a1, string b1){

    a = a1;
    b = b1;

    for(int i = 0; i < a1.size(); i++){
        cnts1[i + 1][0] = cnts1[i][0];
        cnts1[i + 1][1] = cnts1[i][1];
        cnts1[i + 1][2] = cnts1[i][2];

        cnts2[i + 1][0] = cnts2[i][0];
        cnts2[i + 1][1] = cnts2[i][1];
        cnts2[i + 1][2] = cnts2[i][2];

        list_n[i + 1][0] = list_n[i][0];
        list_n[i + 1][1] = list_n[i][1];
        list_n[i + 1][2] = list_n[i][2];
        list_n[i + 1][3] = list_n[i][3];
        list_n[i + 1][4] = list_n[i][4];
        list_n[i + 1][5] = list_n[i][5];


        if(a1[i] == 'A'){
            cnts1[i + 1][0]++;
            if(b1[i] == 'A'){
                cnts2[i + 1][0]++;
            }else if(b1[i] == 'T'){
                cnts2[i + 1][1]++;
                list_n[i + 1][0]++;
            }else{
                cnts2[i + 1][2]++;
                list_n[i + 1][2]++;
            }
        }else if(a1[i] == 'T'){

            cnts1[i + 1][1]++;
            if(b1[i] == 'T'){
                cnts2[i + 1][1]++;
            }else if(b1[i] == 'A'){
                cnts2[i + 1][0]++;
                list_n[i + 1][1]++;
            }else{
                cnts2[i + 1][2]++;
                list_n[i + 1][4]++;
            }


        }else{

            cnts1[i + 1][2]++;
            if(b1[i] == 'C'){
                cnts2[i + 1][2]++;
            }else if(b1[i] == 'A'){
                cnts2[i + 1][0]++;
                list_n[i + 1][3]++;
            }else{
                cnts2[i + 1][1]++;
                list_n[i + 1][5]++;
            }

        }
    }

}

int get_distance(int x, int y){

    int total = 0;



    if(cnts2[y + 1][0] - cnts2[x][0] != cnts1[y + 1][0] - cnts1[x][0]){
        return -1;
    }

    if(cnts2[y + 1][1] - cnts2[x][1] != cnts1[y + 1][1] - cnts1[x][1]){
        return -1;
    }

    if(cnts2[y + 1][2] - cnts2[x][2] != cnts1[y + 1][2] - cnts1[x][2]){
        return -1;
    }



    total += min(list_n[y + 1][0] - list_n[x][0], list_n[y + 1][1] - list_n[x][1]);
    total += abs((list_n[y + 1][0] - list_n[x][0]) - (list_n[y + 1][1] - list_n[x][1])) * 2;
    total += min(list_n[y + 1][2] - list_n[x][2], list_n[y + 1][3] - list_n[x][3]);

    total += min(list_n[y + 1][4] - list_n[x][4], list_n[y + 1][5] - list_n[x][5]);


    return total;



}

Compilation message (stderr)

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

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