제출 #1240982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240982		luka_zecevic	Mutating DNA (IOI21_dna)	C++20	100 / 100	23 ms	7176 KiB

dna

#include "bits/stdc++.h"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff first
#define ss second
#define ll long long
using namespace std;

const int N = 1e5 + 10;
int C[2][N], A[2][N], T[2][N];
int AC[N], CA[N], CT[N], TC[N], AT[N], TA[N];
int n;

void init(string a, string b)
{
    n = (int)a.size();
    for(int i = 1; i <= n; i++)
    {
        A[0][i] = A[0][i - 1] + (a[i - 1] == 'A');
        A[1][i] = A[1][i - 1] + (b[i - 1] == 'A');

        C[0][i] = C[0][i - 1] + (a[i - 1] == 'C');
        C[1][i] = C[1][i - 1] + (b[i - 1] == 'C');

        T[0][i] = T[0][i - 1] + (a[i - 1] == 'T');
        T[1][i] = T[1][i - 1] + (b[i - 1] == 'T');

        AC[i] = AC[i - 1] + (a[i - 1] == 'A' && b[i - 1] == 'C');
        CA[i] = CA[i - 1] + (a[i - 1] == 'C' && b[i - 1] == 'A');

        AT[i] = AT[i - 1] + (a[i - 1] == 'A' && b[i - 1] == 'T');
        TA[i] = TA[i - 1] + (a[i - 1] == 'T' && b[i - 1] == 'A');

        CT[i] = CT[i - 1] + (a[i - 1] == 'C' && b[i - 1] == 'T');
        TC[i] = TC[i - 1] + (a[i - 1] == 'T' && b[i - 1] == 'C');

    }
}

int get_distance(int x, int y)
{
    x++; y++;
    if( C[0][y] - C[0][x - 1] != C[1][y] - C[1][x - 1] || 
        A[0][y] - A[0][x - 1] != A[1][y] - A[1][x - 1] ||
        T[0][y] - T[0][x - 1] != T[1][y] - T[1][x - 1] ) return -1;

    int a = min(AC[y] - AC[x - 1], CA[y] - CA[x - 1]) +
            min(AT[y] - AT[x - 1], TA[y] - TA[x - 1]) +
            min(TC[y] - TC[x - 1], CT[y] - CT[x - 1]);
    
    int b = ( max(AC[y] - AC[x - 1], CA[y] - CA[x - 1]) - min(AC[y] - AC[x - 1], CA[y] - CA[x - 1]) +
              max(AT[y] - AT[x - 1], TA[y] - TA[x - 1]) - min(AT[y] - AT[x - 1], TA[y] - TA[x - 1]) +
              max(TC[y] - TC[x - 1], CT[y] - CT[x - 1]) - min(TC[y] - TC[x - 1], CT[y] - CT[x - 1]) ) * 2 / 3;
              
    return a + b;
}

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