제출 #519392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519392		aris12345678	DNA 돌연변이 (IOI21_dna)	C++17	0 / 100	48 ms	6048 KiB

dna

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

const int mxN = 1e5+5;
string s, t;
int pref[mxN][3][2];

void init(string a, string b) {
    int n = int(a.size());
    s = a, t = b;
    for(int i = 0; i < n; i++) {
        pref[i][0][0] = pref[i-1][0][0], pref[i][1][0] = pref[i-1][1][0], pref[i][2][0] = pref[i-1][2][0];
        if(s[i] == 'A')
            pref[i][0][0]++;
        else if(s[i] == 'C')
            pref[i][1][0]++;
        else
            pref[i][2][0]++;
    }
    for(int i = 0; i < n; i++) {
        pref[i][0][1] = pref[i-1][0][1], pref[i][1][1] = pref[i-1][1][1], pref[i][2][1] = pref[i-1][2][1];
        if(t[i] == 'A')
            pref[i][0][1]++;
        else if(t[i] == 'C')
            pref[i][1][1]++;
        else
            pref[i][2][1]++;
    }
}

int ceil(int a, int b) {
    return a%b == 0 ? a/b : a/b+1;
}

int cast(char c) {
    if(c == 'A')
        return 0;
    if(c == 'C')
        return 1;
    return 2;
}

int get_distance(int x, int y) {
    int n = (y-x+1);
    string a = s.substr(x, n), b = t.substr(x, n);
    // cout << a << " " << b << "\n";
    // cout << "A: " << pref[y][0][0]-pref[x-1][0][0] << " " << pref[y][0][1]-pref[x-1][0][1] << "\n";
    // cout << "C: " << pref[y][1][0]-pref[x-1][1][0] << " " << pref[y][1][1]-pref[x-1][1][1] << "\n";
    // cout << "T: " << pref[y][2][0]-pref[x-1][2][0] << " " << pref[y][2][1]-pref[x-1][2][1] << "\n";
    if(pref[y][0][0]-pref[x-1][0][0] != pref[y][0][1]-pref[x-1][0][1])
        return -1;
    if(pref[y][1][0]-pref[x-1][1][0] != pref[y][1][1]-pref[x-1][1][1])
        return -1;
    if(pref[y][2][0]-pref[x-1][2][0] != pref[y][2][1]-pref[x-1][2][1])
        return -1;
    deque<int> d[3];
    for(int i = 0; i < n; i++) {
        if(b[i] == 'A')
            d[0].push_back(i);
        else if(b[i] == 'C')
            d[1].push_back(i);
        else
            d[2].push_back(i);
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == b[i])
            d[cast(a[i])].pop_front();
        else {
            swap(a[i], a[d[cast(a[i])].front()]);
            ans++;
            if(a[i] == b[i])
                d[cast(a[i])].pop_front();
        }
    }
    return ans;
}

// int main() {
//     string a, b;
//     cin >> a >> b;
//     init(a, b);
//     int q;
//     scanf("%d", &q);
//     while(q--) {
//         int x, y;
//         scanf("%d %d", &x, &y);
//         printf("%d\n", get_distance(x, y));
//     }
//     return 0;
// }

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