Submission #1238880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238880		vtnoo	DNA 돌연변이 (IOI21_dna)	C++20	71 / 100	1596 ms	2380 KiB

dna

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

const int MAXN=100005;
int N;
string s, z, s_, z_;
map<char,int> cnt, cnt2;

void init(string a_, string b_){
	N=a_.size();
	s_=a_;
	z_=b_;
}

int get_distance(int x, int y){
	s=s_;
	z=z_;
	cnt.clear();
	cnt2.clear();
	vector<bool> listo(N, false);
	for(int i=x;i<=y;i++){
		//~ cout<<s[i]<<" "<<z[i]<<endl;
		cnt[s[i]]++;
		cnt2[z[i]]++;
		if(s[i]==z[i])listo[i]=true;
	}
	int ans=0;
	if(cnt.size()!=cnt2.size())return -1;
	for(int i=x;i<=y;i++){
		if(listo[i])continue;
		if(s[i]!=z[i]){
			bool ok=false;
			for(int j=x;j<=y;j++){
				if(i==j)continue;
				if(listo[j])continue;
				if(z[i]==s[j]&&s[i]==z[j]){
					ok=true;
					ans++;
					swap(s[j], s[i]);
					listo[i]=listo[j]=true;
					break;
				}
			}
			if(ok)continue;
			for(int j=x;j<=y;j++){
				if(i==j)continue;
				if(listo[j])continue;
				if(z[i]==s[j]){
					ok=true;
					ans++;
					swap(s[i], s[j]);
					listo[i]=true;
					break;
				}
			}
		}
	}
	for(int i=x;i<=y;i++)if(s[i]!=z[i])return -1;
	return ans;
}

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