Submission #499050

#	Time	Username	Problem	Language	Result	Execution time	Memory
499050		Khizri	Mutating DNA (IOI21_dna)	C++17	100 / 100	420 ms	51080 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
string a,b;
char xx[10]={'A','A','A','C','C','C','T','T','T'};
char yy[10]={'A','C','T','A','C','T','A','C','T'};
vector<pair<int,pair<string,string>>>vt;
map<pair<char,char>,int>MP[100050];
void funk(vector<int>vtt){
    string a,b;
    for(int v:vtt){
        a+=xx[v];
        b+=yy[v];
    }
    string qa=a,qb=b;
    sort(all(qa));
    sort(all(qb));
    if(qa!=qb){
        return;
    }
    int ans=0;
    string ca=a,cb=b;
    while(a!=b){
        for(int i=0;i<a.size();i++){
            for(int j=i+1;j<b.size();j++){
                if(a[i]!=b[i]&&a[j]!=b[j]){
                    if(a[i]==b[j]&&a[j]==b[i]){
                        swap(a[i],a[j]);
                        ans++;
                    }
                }
            }
        }
        for(int i=0;i<a.size();i++){
            for(int j=i+1;j<b.size();j++){
                if(a[i]!=b[i]&&a[j]!=b[j]){
                    if(b[i]==a[j]){
                        swap(a[i],a[j]);
                        ans++;
                    }
                }
            }
        }
    }
    vt.pb({ans,{ca,cb}});
}
void init(std::string ax, std::string ay) {
    a=ax,b=ay;
    for(int i=0;i<9;i++){
        funk({i});
    }
    for(int i=0;i<9;i++){
        for(int j=i;j<9;j++){
            funk({i,j});
        }
    }
    for(int i=0;i<9;i++){
        for(int j=i;j<9;j++){
            for(int k=j;k<9;k++){
                funk({i,j,k});
            }
        }
    }
    sort(all(vt));
    for(int i=0;i<a.size();i++){
        if(i>0){
            MP[i]=MP[i-1];
        }
        MP[i][{a[i],b[i]}]++;
    }
}

int get_distance(int l, int r) {
    int a1=0,a2=0,a3=0,b1=0,b2=0,b3=0;
    map<pair<char,char>,int>mp;
    mp=MP[r];
    if(l>0){
        for(auto it=mp.begin();it!=mp.end();it++){
            mp[it->F]-=MP[l-1][it->F];
        }
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        char q=it->F.F;
        int cost=it->S;
        if(q=='A'){
            a1+=cost;
        }
        else if(q=='C'){
            a2+=cost;
        }
        else{
            a3+=cost;
        }
        q=it->F.S;
        if(q=='A'){
            b1+=cost;
        }
        else if(q=='C'){
            b2+=cost;
        }
        else{
            b3+=cost;
        }
    }
    if(a1!=b1||a2!=b2||a3!=b3){
        return -1;
    }
	int ans=0;
	for(int i=0;i<vt.size();i++){
        string x=vt[i].S.F,y=vt[i].S.S;
        int k=vt[i].F;
        int cost=1e7;
        for(int i=0;i<x.size();i++){
            cost=min(cost,mp[{x[i],y[i]}]);
        }
        if(cost>0){
            for(int i=0;i<x.size();i++){
                mp[{x[i],y[i]}]-=cost;
            }
            ans+=cost*k;
        }
	}
	for(auto it=mp.begin();it!=mp.end();it++){
        ans+=it->S;
	}
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void funk(std::vector<int>)':
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<a.size();i++){
      |                     ~^~~~~~~~~
dna.cpp:30:28: 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 j=i+1;j<b.size();j++){
      |                           ~^~~~~~~~~
dna.cpp:39:22: 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=0;i<a.size();i++){
      |                     ~^~~~~~~~~
dna.cpp:40:28: 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 j=i+1;j<b.size();j++){
      |                           ~^~~~~~~~~
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:114:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for(int i=0;i<vt.size();i++){
      |              ~^~~~~~~~~~
dna.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int i=0;i<x.size();i++){
      |                     ~^~~~~~~~~
dna.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for(int i=0;i<x.size();i++){
      |                         ~^~~~~~~~~

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