제출 #1002097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002097		vjudge1	DNA 돌연변이 (IOI21_dna)	C++17	0 / 100	80 ms	9804 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int sze=1e5+10;

map<string,vector<int>> pref;

struct node{
	int A=0;
	int T=0;
	int C=0;
};

node ap[sze];
node bp[sze];
string s,t;

void init(string a, string b) {
	
	int n = a.size();
	vector<char> lst={'A','C','T'};
	for(auto v:lst){
		for(auto x:lst){
			// cout<<to_string(v+x)<<endl;
			string t="";
			t+=v;
			t+=x;
			// cout<<t<<endl;
			pref[t].resize(n+1,0);
		}	
	}
	a='-'+a;
	b='-'+b;
	s=a;
	t=b;

	for(int i=1;i<=n;i++){
		string t2 = "";
		t2+=a[i];
		t2+=b[i];
		// cout<<x<<endl;
		for(auto v:lst){
			for(auto x:lst){
				// cout<<to_string(v+x)<<endl;
				string t="";
				t+=v;
				t+=x;
				// cout<<t<<endl;
				pref[t][i]+=pref[t][i-1];
				// cout<<pref[t][i-1]<<endl;
			}	
		}
		// cout<<x<<endl;
		pref[t2][i]++;
		// cout<<t2<<endl;

		ap[i]=ap[i-1];
		bp[i]=bp[i-1];

		if(a[i]=='A'){
			ap[i].A++;
		}
		else if(a[i]=='C'){
			ap[i].C++;
		}
		else if(a[i]=='T'){
			ap[i].T++;
		}
		if(b[i]=='A'){
			bp[i].A++;
		}
		else if(b[i]=='C'){
			bp[i].C++;
		}
		else if(b[i]=='T'){
			bp[i].T++;
		}
	}

}

int get_distance(int x, int y) {
	// cout<<varA['A'].size()<<endl;
	x++;
	y++;

	int ara_a = ap[y].A-ap[x-1].A;
	int ara_c = ap[y].C-ap[x-1].C;
	int ara_t = ap[y].T-ap[x-1].T;

	int bra_a = bp[y].A-bp[x-1].A;
	int bra_c = bp[y].C-bp[x-1].C;
	int bra_t = bp[y].T-bp[x-1].T;
	// if(y-x<=2){

	// 	if(y==x){
	// 		if(s[x]!=t[x]){
	// 			return 1;
	// 		}
	// 		else{
	// 			return 0;
	// 		}
	// 	}
	// 	else if( y==x+1 ){

	// 		if(s[x]==t[x] && s[y]==t[y]){
	// 			return 0;
	// 		}
	// 		if(s[x]==t[x] && s[y]!=t[y]){
	// 			return 1;
	// 		}
	// 		else if(s[y]==t[y] && s[x]!=t[x]){
	// 			return 1;
	// 		}
	// 		else if(s[x]==t[y] && t[x]==s[y]){
	// 			return 1;
	// 		}
	// 	}
	// 	// blabla
		

	// }
	if(ara_a!=bra_a || ara_c!=bra_c || ara_t!=bra_t){
		// cout<<x<<" "<<y<<endl;
		// cout<<ara_a<<" "<<bra_a<<" "<<ara_c<<" "<<bra_c<<" "<<ara_t<<" "<<bra_t<<endl;
		return -1;
	}
	int cev= 0;
	// cout<<pref["AA"][y] - pref["AA"][x-1]<<" "<<pref["CC"][y] - pref["CC"][x-1]<<" "<<pref["TT"][y] - pref["TT"][x-1]<<endl;

	// cout<<cev<<endl;
	cev+= (max(pref["AT"][y]-pref["AT"][x-1],pref["TA"][y] - pref["TA"][x-1])+1) /2;
	return cev;
}

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