Submission #446919

#	Time	Username	Problem	Language	Result	Execution time	Memory
446919		Deepesson	Mutating DNA (IOI21_dna)	C++17	100 / 100	144 ms	10432 KiB

dna

#include <bits/stdc++.h>
#define MAX 105000
#include "dna.h"

int ps[3][2][MAX];
int dest[3][3][MAX];
void prefix_sum(int* arr,int n){
    int count = 0;
    for(int i=0;i!=n;++i){
        count+=*arr;
        *arr=count;
        ++arr;
    }
}
int get_segment(int*arr,int l,int r) {
    --l;
    int res = 0;
    if(l>=0)res-=arr[l];
    res+=arr[r];
    return res;
}
void init(std::string a,std::string b){
    std::vector<int> v1,v2;
    for(auto&x:a){
        if(x=='A')v1.push_back(0);
        else if(x=='T')v1.push_back(1);
        else v1.push_back(2);
    }
    for(auto&x:b){
        if(x=='A')v2.push_back(0);
        else if(x=='T')v2.push_back(1);
        else v2.push_back(2);
    }
    for(int i=0;i!=v1.size();++i){
        ps[v1[i]][0][i]++;
        ps[v2[i]][1][i]++;
        if(v1[i]!=v2[i]){
            dest[v1[i]][v2[i]][i]++;
        }
    }
    for(int i=0;i!=3;++i){
        prefix_sum(&ps[i][0][0],MAX-3);
        prefix_sum(&ps[i][1][0],MAX-3);
    }
    for(int i=0;i!=3;++i){
        for(int j=0;j!=3;++j){
            prefix_sum(&dest[i][j][0],MAX-3);
        }
    }
}
int get_distance(int x,int y){
    for(int i=0;i!=3;++i){
        if(get_segment(&ps[i][0][0],x,y)!=get_segment(&ps[i][1][0],x,y)){
            return -1;
        }
    }
    int tabela[3][3];
    for(int i=0;i!=3;++i){
        for(int j=0;j!=3;++j){
            tabela[i][j]=get_segment(&dest[i][j][0],x,y);
        }
    }
    int custo = 0;
    for(int i=0;i!=3;++i){
        for(int j=0;j!=3;++j){
            int min = std::min(tabela[i][j],tabela[j][i]);
            custo+=min;
            tabela[i][j]-=min;
            tabela[j][i]-=min;
        }
    }
    for(int __=0;__!=5;++__)
    for(int i=0;i!=3;++i){
        for(int j=0;j!=3;++j){
            for(int k=0;k!=3;++k){
                int min = std::min(tabela[i][j],std::min(tabela[j][k],tabela[k][i]));
                custo+=min*2;
                tabela[i][j]-=min;
                tabela[j][k]-=min;
                tabela[k][i]-=min;
            }
        }
    }
    return custo;
}

Compilation message (stderr)

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

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