제출 #584736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584736		rc_catunta	DNA 돌연변이 (IOI21_dna)	C++17	22 / 100	1584 ms	6824 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);
}

int get_distance(int x, int y) {
    int res = 0;
	a = sa;
    b = sb;
	// SUBTASK 1,2 y 4
    vector<int>::iterator it;
    int pos;
    //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{
                res++;
                if(a[i]=='A' and b[i]=='C'){
                    // Buscamos algo que mate dos pajaros de un tiro
                    it = upper_bound(CA.begin(),CA.end(),i);
                    if(it!=CA.end()){
                        pos = *it;
                        while(a[pos]==b[pos]){
                            it++;
                            if(it==CA.end()) break;
                            pos = *it;
                        }
                        if(it!=CA.end() and pos<=y){
                            swap(b[i],b[pos]);
                            continue;
                        }
                    }
                    // Buscar cualquier letra que sirva
                    it = upper_bound(SA.begin(),SA.end(),i);
                    pos = *it;
                    while(a[pos]==b[pos]){
                        it++;
                        if(it==SA.end()) break;
                        pos = *it;
                    }
                    if(it!=SA.end() and pos<=y){
                        swap(b[i],b[pos]);
                        continue;
                    }
                }
                if(a[i]=='A' and b[i]=='T'){
                    // Buscamos algo que mate dos pajaros de un tiro
                    it = upper_bound(TA.begin(),TA.end(),i);
                    if(it!=TA.end()){
                        pos = *it;
                        while(a[pos]==b[pos]){
                            it++;
                            if(it==TA.end()) break;
                            pos = *it;
                        }
                        if(it!=TA.end() and pos<=y){
                            swap(b[i],b[pos]);
                            continue;
                        }
                    }
                    // Buscar cualquier letra que sirva
                    it = upper_bound(SA.begin(),SA.end(),i);
                    pos = *it;
                    while(a[pos]==b[pos]){
                        it++;
                        if(it==SA.end()) break;
                        pos = *it;
                    }
                    if(it!=SA.end() and pos<=y){
                        swap(b[i],b[pos]);
                        continue;
                    }
                }
                if(a[i]=='C' and b[i]=='A'){
                    // Buscamos algo que mate dos pajaros de un tiro
                    it = upper_bound(AC.begin(),AC.end(),i);
                    if(it!=AC.end()){
                        pos = *it;
                        while(a[pos]==b[pos]){
                            it++;
                            if(it==AC.end()) break;
                            pos = *it;
                        }
                        if(it!=AC.end() and pos<=y){
                            swap(b[i],b[pos]);
                            continue;
                        }
                    }
                    // Buscar cualquier letra que sirva
                    it = upper_bound(SC.begin(),SC.end(),i);
                    pos = *it;
                    while(a[pos]==b[pos]){
                        it++;
                        if(it==SC.end()) break;
                        pos = *it;
                    }
                    if(it!=SC.end() and pos<=y){
                        swap(b[i],b[pos]);
                        continue;
                    }
                }
                if(a[i]=='C' and b[i]=='T'){
                    // Buscamos algo que mate dos pajaros de un tiro
                    it = upper_bound(TC.begin(),TC.end(),i);
                    if(it!=TC.end()){
                        pos = *it;
                        while(a[pos]==b[pos]){
                            it++;
                            if(it==TC.end()) break;
                            pos = *it;
                        }
                        if(it!=TC.end() and pos<=y){
                            swap(b[i],b[pos]);
                            continue;
                        }
                    }
                    // Buscar cualquier letra que sirva
                    it = upper_bound(SC.begin(),SC.end(),i);
                    pos = *it;
                    while(a[pos]==b[pos]){
                        it++;
                        if(it==SC.end()) break;
                        pos = *it;
                    }
                    if(it!=SC.end() and pos<=y){
                        swap(b[i],b[pos]);
                        continue;
                    }
                }
                if(a[i]=='T' and b[i]=='A'){
                    // Buscamos algo que mate dos pajaros de un tiro
                    it = upper_bound(AT.begin(),AT.end(),i);
                    if(it!=AT.end()){
                        pos = *it;
                        while(a[pos]==b[pos]){
                            it++;
                            if(it==AT.end()) break;
                            pos = *it;
                        }
                        if(it!=AT.end() and pos<=y){
                            swap(b[i],b[pos]);
                            continue;
                        }
                    }
                    // Buscar cualquier letra que sirva
                    it = upper_bound(ST.begin(),ST.end(),i);
                    pos = *it;
                    while(a[pos]==b[pos]){
                        it++;
                        if(it==ST.end()) break;
                        pos = *it;
                    }
                    if(it!=ST.end() and pos<=y){
                        swap(b[i],b[pos]);
                        continue;
                    }
                }
                if(a[i]=='T' and b[i]=='C'){
                    // Buscamos algo que mate dos pajaros de un tiro
                    it = upper_bound(CT.begin(),CT.end(),i);
                    if(it!=CT.end()){
                        pos = *it;
                        while(a[pos]==b[pos]){
                            it++;
                            if(it==CT.end()) break;
                            pos = *it;
                        }
                        if(it!=CT.end() and pos<=y){
                            swap(b[i],b[pos]);
                            continue;
                        }
                    }
                    // Buscar cualquier letra que sirva
                    it = upper_bound(ST.begin(),ST.end(),i);
                    pos = *it;
                    while(a[pos]==b[pos]){
                        it++;
                        if(it==ST.end()) break;
                        pos = *it;
                    }
                    if(it!=ST.end() and pos<=y){
                        swap(b[i],b[pos]);
                        continue;
                    }
                }
            }
        }
        return res;
    }
    else return -1;

}

컴파일 시 표준 에러 (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: 22 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16