Submission #584734

#	Time	Username	Problem	Language	Result	Execution time	Memory
584734		rc_catunta	Mutating DNA (IOI21_dna)	C++17	0 / 100	1573 ms	522976 KiB

dna

#include "dna.h"
#include <algorithm>
#include <vector>
#include <set>
#include <iostream>
using namespace std;

string sa, sb, a, b;
vector<int> acuma1,acuma2,acumt1,acumt2,acumc1,acumc2;
vector<int> AC, AT, CA, CT, TA, TC, SA, SC, ST;

void init(string a, string b) {
	sa = a;
	sb = b;
	// Construimos la tabla de acumuladas
	acuma1.assign(a.size(),0);
	acumt1.assign(a.size(),0);
    acumc1.assign(a.size(),0);
	acuma2.assign(a.size(),0);
	acumt2.assign(a.size(),0);
    acumc2.assign(a.size(),0);
	for(int i=0;i<a.size();i++){
		// Acum A para el string 1
		if(a[i]=='A') acuma1[i]++;
		if(i>0) acuma1[i]+=acuma1[i-1];
		// Acum A para el string 2
		if(b[i]=='A'){
            acuma2[i]++;
            SA.push_back(i);
        }
        if(i>0) acuma2[i]+=acuma2[i-1];
		// Acum T para el string 1
		if(a[i]=='T') acumt1[i]++;
		if(i>0) acumt1[i]+=acumt1[i-1];
		// Acum T para el string 2
		if(b[i]=='T'){
            acumt2[i]++;
            ST.push_back(i);
        }
        if(i>0) acumt2[i]+=acumt2[i-1];
        // Acum C para el string 1
		if(a[i]=='C') acumc1[i]++;
		if(i>0) acumc1[i]+=acumc1[i-1];
		// Acum C para el string 2
		if(b[i]=='C'){
            acumc2[i]++;
            SC.push_back(i);
        }
        if(i>0) acumc2[i]+=acumc2[i-1];
        // Preproceso
        if(a[i]=='A' and b[i]=='C') AC.push_back(i);
        if(a[i]=='A' and b[i]=='T') AT.push_back(i);
        if(a[i]=='C' and b[i]=='A') CA.push_back(i);
        if(a[i]=='C' and b[i]=='T') CT.push_back(i);
        if(a[i]=='T' and b[i]=='A') TA.push_back(i);
        if(a[i]=='T' and b[i]=='C') TC.push_back(i);
	}
}

bool posible_transformar(int x, int y){
	int ca1 = acuma1[y];
    if(x>0) ca1 -= acuma1[x-1];
    int ca2 = acuma2[y];
    if(x>0) ca2 -= acuma2[x-1];
    int cc1 = acumc1[y];
    if(x>0) cc1 -= acumc1[x-1];
    int cc2 = acumc2[y];
    if(x>0) cc2 -= acumc2[x-1];
    int ct1 = acumt1[y];
    if(x>0) ct1 -= acumt1[x-1];
    int ct2 = acumt2[y];
    if(x>0) ct2 -= acumt2[x-1];
    return (ca1==ca2 and cc1 == cc2 and ct1 == ct2);
}

void cambio(char c1, char c2, int y, int i){
    vector<int>::iterator it;
    int pos;
    vector<int> doble,simple;
    // TO-DO quien es doble y simple
    if(a[i]=='A' and b[i]=='C'){
        doble = CA;
        simple = SA;
    }
    if(a[i]=='A' and b[i]=='T'){
        doble = TA;
        simple = SA;
    }
    if(a[i]=='C' and b[i]=='A'){
        doble = AC;
        simple = SC;
    }
    if(a[i]=='C' and b[i]=='T'){
        doble = TC;
        simple = SC;
    }
    if(a[i]=='T' and b[i]=='A'){
        doble = AT;
        simple = ST;
    }
    if(a[i]=='T' and b[i]=='C'){
        doble = CT;
        simple = ST;
    }
    // Buscamos algo que mate dos pajaros de un tiro
    it = upper_bound(doble.begin(),doble.end(),i);
    if(it!=doble.end()){
        pos = *it;
        while(a[pos]==b[pos]){
            it++;
            if(it==doble.end()) break;
            pos = *it;
        }
        if(it!=doble.end() and pos<=y){
            swap(b[i],b[pos]);
            return;
        }
    }
    // Buscar cualquier A
    it = upper_bound(simple.begin(),simple.end(),i);
    pos = *it;
    while(a[pos]==b[pos]){
        it++;
        if(it==simple.end()) break;
        pos = *it;
    }
    if(it!=simple.end() and pos<=y){
        swap(b[i],b[pos]);
        return;
    }
}

int get_distance(int x, int y) {
    int res = 0;
	a = sa;
    b = sb;
	// SUBTASK 1,2 y 4
    cout<<"Caso "<<x<<" "<<y<<"\n";
	if(posible_transformar(x,y)){
        for(int i=x;i<=y;i++){ // O(n)
            if(a[i]==b[i]) continue;
            else{
                cambio(a[i],b[i],y,i);
                cout<<"-----------\n";
                cout<<a<<"\n";
                cout<<b<<"\n";
                res++;
            }
        }
        return res;
    }
    else return -1;

}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<a.size();i++){
      |              ~^~~~~~~~~
dna.cpp:31:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   31 |         if(i>0) acuma2[i]+=acuma2[i-1];
      |         ^~
dna.cpp:33:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |   if(a[i]=='T') acumt1[i]++;
      |   ^~

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