Submission #499046

#	Time	Username	Problem	Language	Result	Execution time	Memory
499046		Khizri	Mutating DNA (IOI21_dna)	C++17	71 / 100	1561 ms	3752 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;
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));
}

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;
    for(int i=l;i<=r;i++){
        mp[{a[i],b[i]}]++;
        if(a[i]=='A'){
            a1++;
        }
        else if(a[i]=='C'){
            a2++;
        }
        else{
            a3++;
        }
        if(b[i]=='A'){
            b1++;
        }
        else if(b[i]=='C'){
            b2++;
        }
        else{
            b3++;
        }
    }
    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=1000;
        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:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i=0;i<a.size();i++){
      |                     ~^~~~~~~~~
dna.cpp:29:28: 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 j=i+1;j<b.size();j++){
      |                           ~^~~~~~~~~
dna.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i=0;i<a.size();i++){
      |                     ~^~~~~~~~~
dna.cpp:39:28: 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 j=i+1;j<b.size();j++){
      |                           ~^~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:99: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]
   99 |  for(int i=0;i<vt.size();i++){
      |              ~^~~~~~~~~~
dna.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int i=0;i<x.size();i++){
      |                     ~^~~~~~~~~
dna.cpp:107:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             for(int i=0;i<x.size();i++){
      |                         ~^~~~~~~~~

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