제출 #1142029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142029		programming23	Mutating DNA (IOI21_dna)	C++20	0 / 100	1612 ms	1769640 KiB

dna

#include "bits/stdc++.h"
using namespace std;

string stringA="";
string stringB="";
map<string, int> answers;

void init(string a, string b) {
	stringA = a;
	stringB = b;
}

int get_distance(int x, int y) {
	string sA = stringA;
	string sB = stringB;
	map<char, int> countsB;
	map<char, int> countsA;
	int count = 0;
	for(int i=x; i <= y; i++){
		if(countsA.find(sA[i]) == countsA.end()){
			countsA[sA[i]] = 1;
		}else{
			countsA[sA[i]] +=1;
		}
		if(countsB.find(sB[i]) == countsB.end()){
			countsB[sB[i]] = 1;
		}else{
			countsB[sB[i]] +=1;
		}
	}
    int lnA = countsA.size();
    int lnB = countsB.size();
	if(lnA != lnB){
		return -1;
	}for(auto c: countsA){
		if(countsA[c.first] != countsB[c.first]){
			return -1;
		}
	}
    int i=x;
    while (i <= y && sA != sB){
        char c = sA[i];
        string t = sA.substr(i, y) + ":"+sB.substr(i, y) ;
        if(answers.find(t) != answers.end()){
            count += answers[t];
            break;
        }
        if(c == sB[i]){
            i++;
            continue;
        }
        for(int z=i+1; z <= y; z++){
            if(sA[z] != sB[i] || sA[z] == sB[z]){
                continue;
            }
            sA[i] = sA[z];
            sA[z] = c;
            if(lnA == 2 && lnB == 2){
                i = z+1;
            }
            else{
                i++;
            }
            count++;
        }
    }
    answers[sA.substr(x, y) + ":" + sB.substr(x, y)] = count;
	return count;
}

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