제출 #1224173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224173		guagua0407	Mutating DNA (IOI21_dna)	C++20	100 / 100	71 ms	33352 KiB

dna

#include "dna.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const int mxn=1e5+5;
    vector<vector<vector<int>>> pre(mxn,vector<vector<int>>(3,vector<int>(3)));
    vector<vector<int>> prea(mxn,vector<int>(3));
    vector<vector<int>> preb(mxn,vector<int>(3));
}

void init(std::string A, std::string B) {
    int n=(int)A.size();
    map<char,int> mp;
    mp['A']=0;
    mp['C']=1;
    mp['T']=2;
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;i++){
        a[i]=mp[A[i-1]];
        b[i]=mp[B[i-1]];
    }
    for(int i=1;i<=n;i++){
        pre[i][b[i]][a[i]]++;
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                pre[i][j][k]+=pre[i-1][j][k];
            }
        }
        prea[i][a[i]]++;
        preb[i][b[i]]++;
        for(int j=0;j<3;j++){
            prea[i][j]+=prea[i-1][j];
            preb[i][j]+=preb[i-1][j];
        }
    }
}

int get_distance(int x, int y) {
    x++;
    y++;
    for(int j=0;j<3;j++){
        if((prea[y][j]-prea[x-1][j])!=(preb[y][j]-preb[x-1][j])) return -1;
    }
    vector<vector<int>> res(3,vector<int>(3));
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            res[i][j]=pre[y][i][j]-pre[x-1][i][j];
        }
    }
    int ans=0;
    for(int i=0;i<3;i++){
        for(int j=i+1;j<3;j++){
            int mn=min(res[i][j],res[j][i]);
            ans+=mn;
            res[i][j]-=mn;
            res[j][i]-=mn;
        }
    }
    if(res[0][1]>0){
        int val=res[0][1];
        if(res[1][2]!=val or res[2][0]!=val) return -1;
        if(res[1][0]!=0 or res[0][2]!=0 or res[2][1]!=0) return -1;
        ans+=res[0][1]*2;
    }
    else if(res[1][0]>0){
        int val=res[1][0];
        if(res[0][2]!=val or res[2][1]!=val) return -1;
        if(res[0][1]!=0 or res[1][2]!=0 or res[2][0]!=0) return -1;
        ans+=res[1][0]*2;
    }
	return ans;
}

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