제출 #1142621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142621		redamoi	Mutating DNA (IOI21_dna)	C++20	100 / 100	283 ms	206408 KiB

dna

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

vector<map<string,int>> MEM(1e6);

vector<vector<int>> freq1(1e6,vector<int>(3,0));
vector<vector<int>> freq2(1e6,vector<int>(3,0));

void init(string a, string b){
    string ax=a,bx=b;
    string A[6] = {"AT","TA","AC","CA","CT","TC"};
    string s;
    for(auto x:A){
       s="";
       s+=a[0];
       s+=b[0];
       if(s==x)MEM[0][x]=1;
       else MEM[0][x]=0;
    }
    if(a[0]=='A')freq1[0][0]++;
    if(a[0]=='C')freq1[0][1]++;
    if(a[0]=='T')freq1[0][2]++;
        
    if(b[0]=='A')freq2[0][0]++;
    if(b[0]=='C')freq2[0][1]++;
    if(b[0]=='T')freq2[0][2]++;
    for(int i=1;i<a.size();i++){
        s = "";
        s+=a[i];
        s+=b[i];
        for(auto x: A){
            if(x==s)MEM[i][x]=MEM[i-1][x]+1;
            else MEM[i][x]=MEM[i-1][x];
        }
        if(a[i]=='A')freq1[i][0]= freq1[i-1][0]+1;
        else freq1[i][0]= freq1[i-1][0];
        
        if(a[i]=='C')freq1[i][1]=freq1[i-1][1]+1;
        else freq1[i][1]=freq1[i-1][1];
        
        if(a[i]=='T')freq1[i][2]=freq1[i-1][2]+1;
        else freq1[i][2]=freq1[i-1][2];
        
        if(b[i]=='A')freq2[i][0]=freq2[i-1][0]+1;
        else freq2[i][0]=freq2[i-1][0];
        
        if(b[i]=='C')freq2[i][1]=freq2[i-1][1]+1;
        else freq2[i][1]=freq2[i-1][1];
        
        if(b[i]=='T')freq2[i][2]=freq2[i-1][2]+1;
        else freq2[i][2]=freq2[i-1][2];
        //cout << freq1[i][0] << endl;
        //cout << freq1[i][1] << endl;
        //cout << freq1[i][2] << endl;
        //cout << freq2[i][0] << endl;
        //cout << freq2[i][1] << endl;
        //cout << freq2[i][2] << endl;
        //cout << endl;
    }
}



int get_distance(int x, int y){
    int ans =0, r =0;
    
    
    if(x==0){
        if(freq1[y][0]!=freq2[y][0] or freq1[y][1]!=freq2[y][1] or freq1[y][2]!=freq2[y][2]) return -1;
        
        ans+=min(MEM[y]["AT"],MEM[y]["TA"]);
        r+=max(MEM[y]["AT"],MEM[y]["TA"])-min(MEM[y]["AT"],MEM[y]["TA"]);
        ans+=min(MEM[y]["AC"],MEM[y]["CA"]);
        r+=max(MEM[y]["AC"],MEM[y]["CA"])-min(MEM[y]["AC"],MEM[y]["CA"]);
        ans+=min(MEM[y]["CT"],MEM[y]["TC"]);
        r+=max(MEM[y]["CT"],MEM[y]["TC"])-min(MEM[y]["CT"],MEM[y]["TC"]);
        ans+=r*2/3;
        return ans;
    }
    
    if(freq1[y][0]-freq1[x-1][0]!=freq2[y][0]-freq2[x-1][0] or freq1[y][1]-freq1[x-1][1]!=freq2[y][1]-freq2[x-1][1] or freq1[y][2]-freq1[x-1][2]!=freq2[y][2]-freq2[x-1][2]) return -1;


    ans+=min(MEM[y]["AT"]-MEM[x-1]["AT"],MEM[y]["TA"]-MEM[x-1]["TA"]);
    r+=max(MEM[y]["AT"]-MEM[x-1]["AT"],MEM[y]["TA"]-MEM[x-1]["TA"])-min(MEM[y]["AT"]-MEM[x-1]["AT"],MEM[y]["TA"]-MEM[x-1]["TA"]);
    ans+=min(MEM[y]["AC"]-MEM[x-1]["AC"],MEM[y]["CA"]-MEM[x-1]["CA"]);
    r+=max(MEM[y]["AC"]-MEM[x-1]["AC"],MEM[y]["CA"]-MEM[x-1]["CA"])-min(MEM[y]["AC"]-MEM[x-1]["AC"],MEM[y]["CA"]-MEM[x-1]["CA"]);
    ans+=min(MEM[y]["CT"]-MEM[x-1]["CT"],MEM[y]["TC"]-MEM[x-1]["TC"]);
    r+=max(MEM[y]["CT"]-MEM[x-1]["CT"],MEM[y]["TC"]-MEM[x-1]["TC"])-min(MEM[y]["CT"]-MEM[x-1]["CT"],MEM[y]["TC"]-MEM[x-1]["TC"]);
    ans+=r*2/3;
    return ans;
}

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