제출 #1324042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324042		sh_qaxxorov_571	Mutating DNA (IOI21_dna)	C++20	100 / 100	22 ms	6104 KiB

dna

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// Prefiks yig'indilari uchun 2D massivlar
// cnt[tur][index] - 6 xil farqli juftliklar sonini saqlaydi
// char_cnt[belgi][index] - har bir belgining sonini saqlaydi
int pref[6][100005];
int c_pref[3][100005]; // 0:A, 1:T, 2:C

void init(string a, string b) {
    int n = a.length();
    for (int i = 0; i < n; i++) {
        // Avvalgi yig'indilarni ko'chirish
        for (int j = 0; j < 6; j++) pref[j][i + 1] = pref[j][i];
        for (int j = 0; j < 3; j++) c_pref[j][i + 1] = c_pref[j][i];

        // Belgilar sonini sanash
        if (a[i] == 'A') c_pref[0][i + 1]++;
        else if (a[i] == 'T') c_pref[1][i + 1]++;
        else c_pref[2][i + 1]++;

        if (b[i] == 'A') c_pref[0][i + 1]--;
        else if (b[i] == 'T') c_pref[1][i + 1]--;
        else c_pref[2][i + 1]--;

        // Juftliklarni aniqlash (faqat farqli bo'lsa)
        if (a[i] != b[i]) {
            if (a[i] == 'A' && b[i] == 'T') pref[0][i + 1]++;
            else if (a[i] == 'A' && b[i] == 'C') pref[1][i + 1]++;
            else if (a[i] == 'T' && b[i] == 'A') pref[2][i + 1]++;
            else if (a[i] == 'T' && b[i] == 'C') pref[3][i + 1]++;
            else if (a[i] == 'C' && b[i] == 'A') pref[4][i + 1]++;
            else if (a[i] == 'C' && b[i] == 'T') pref[5][i + 1]++;
        }
    }
}

int get_distance(int x, int y) {
    // 1. Belgilar soni tengligini tekshirish
    for (int i = 0; i < 3; i++) {
        if (c_pref[i][y + 1] - c_pref[i][x] != 0) return -1;
    }

    // 2. Juftliklar miqdorini olish
    int AT = pref[0][y + 1] - pref[0][x];
    int AC = pref[1][y + 1] - pref[1][x];
    int TA = pref[2][y + 1] - pref[2][x];
    int TC = pref[3][y + 1] - pref[3][x];
    int CA = pref[4][y + 1] - pref[4][x];
    int CT = pref[5][y + 1] - pref[5][x];

    int res = 0;

    // To'g'ridan-to'g'ri almashtirishlar (masalan, AT va TA)
    int m;
    m = min(AT, TA); res += m; AT -= m; TA -= m;
    m = min(AC, CA); res += m; AC -= m; CA -= m;
    m = min(TC, CT); res += m; TC -= m; CT -= m;

    // Siklli almashtirishlar (qolgan juftliklar 3-lik sikl hosil qiladi)
    // Har bir sikl 2 ta almashtirish talab qiladi
    res += (AT + AC + TA + TC + CA + CT) / 3 * 2;

    return res;
}

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