제출 #1001537

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

dna

#include "dna.h"
#include<bits/stdc++.h>
#pragma GCC optimize("-O3")
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pb push_back
#define p_b pop_back
using namespace std;
const ll sz = 1e5+5;
ll cnt[3][sz], cnt2[3][sz], pref[3][3][sz], i, n;
map<char, ll>mp;
void init(string a, string b) {
    a = '#' + a;
    b = '#' + b;
    n = a.size();
    mp['A'] = 0;
    mp['C'] = 1;
    mp['T'] = 2;
    for(i = 1; i <= n; i++)
    {
        for(ll j = 0; j < 3; j++)
        {
            for(ll k = 0; k < 3; k++)
                pref[j][k][i] = pref[j][k][i-1];
        }
        pref[mp[a[i]]][mp[b[i]]][i]++;
    }
    for(i = 1; i <= n; i++)
    {
        cnt[0][i] = cnt[0][i-1];
        cnt[1][i] = cnt[1][i-1];
        cnt[2][i] = cnt[2][i-1];
        cnt2[0][i] = cnt2[0][i-1];
        cnt2[1][i] = cnt2[1][i-1];
        cnt2[2][i] = cnt2[2][i-1];
        if(a[i] == 'A')
            cnt[0][i] = cnt[0][i-1] + 1;
        if(a[i] == 'C')
            cnt[1][i] = cnt[1][i-1] + 1;
        if(a[i] == 'T')
            cnt[2][i] = cnt[2][i-1] + 1;
        if(b[i] == 'A')
            cnt2[0][i] = cnt2[0][i-1] + 1;
        if(b[i] == 'C')
            cnt2[1][i] = cnt2[1][i-1] + 1;
        if(b[i] == 'T')
            cnt2[2][i] = cnt2[2][i-1] + 1;
    }
}

int get_distance(int x, int y) {
	x++, y++;
	ll acnt1 = cnt[0][y] - cnt[0][x-1];
	ll ccnt1 = cnt[1][y] - cnt[1][x-1];
	ll tcnt1 = cnt[2][y] - cnt[2][x-1];
	ll acnt2 = cnt2[0][y] - cnt2[0][x-1];
	ll ccnt2 = cnt2[1][y] - cnt2[1][x-1];
	ll tcnt2 = cnt2[2][y] - cnt2[2][x-1];
	//cout << acnt1 << ' ' << acnt2 << ' ' << ccnt1 << ' ' << ccnt2 << ' ' << tcnt1 << ' ' << tcnt2 << "\n";
	if(acnt1 != acnt2 || ccnt1 != ccnt2 || tcnt1 != tcnt2)
        return -1;
    ll a_t = pref[0][2][y] - pref[0][2][x-1];
    ll t_a = pref[2][0][y] - pref[2][0][x-1];
    ll c_t = pref[1][2][y] - pref[1][2][x-1];
    ll t_c = pref[2][1][y] - pref[2][1][x-1];
    ll a_c = pref[0][1][y] - pref[0][1][x-1];
    ll c_a = pref[1][0][y] - pref[1][0][x-1];
    ll res = 0, minn1, minn2, minn3;
    minn1 = min(a_t, t_a);
    minn2 = min(c_t, t_c);
    minn3 = min(a_c, c_a);
    res += (minn1 + minn2 + minn3);
    a_t -= minn1;
    t_a -= minn1;
    c_t -= minn2;
    t_c -= minn2;
    a_c -= minn3;
    c_a -= minn3;
    ll sum = (a_t + t_a + c_t + t_c + a_c + c_a);
    if(sum)
        res += (sum - 1);
    return res;
}

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