Submission #996411

#	Time	Username	Problem	Language	Result	Execution time	Memory
996411		phoenix	Mutating DNA (IOI21_dna)	C++17	100 / 100	41 ms	7292 KiB

dna

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int pref[ N ][ 3 ][ 3 ];
map<char, int> mp = {
    {'A', 0},
    {'C', 1},
    {'T', 2}
};

void init(string a, string b) {
    int n = (int)a.size();
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < 3;j++) {
            for(int k = 0;k < 3;k++) {
                if(i) pref[ i ][ j ][ k ] = pref[i - 1][ j ][ k ];
                if(mp[a[i]] == j && mp[b[i]] == k) pref[i][j][k]++;
            }
        }
    }
}
int get_distance(int l, int r) {
    int w[3][3] = {};
    int s1[ 3 ] = {}, s2[ 3 ] = {};
    for(int i = 0;i < 3;i++) {
        for(int j = 0;j < 3;j++) {
            w[ i ][ j ] = pref[ r ][ i ][ j ];
            if(l) w[ i ][ j ] -= pref[l - 1][ i ][ j ];
            s1[ i ] += w[ i ][ j ];
            s2[ j ] += w[ i ][ j ];
            // cout << w[ i ][ j ] << ' ';
        }
        // cout << '\n';
    }
    for(int i = 0;i < 3;i++) 
        if(s1[ i ] != s2[ i ]) return -1;
    int res = 0;
    for(int i = 0;i < 3;i++) {
        for(int j = 0;j < 3;j++) {
            if(i == j) continue;
            int c = min(w[ i ][ j ], w[ j ][ i ]);
            res += c;
            w[ i ][ j ] -= c;
            w[ j ][ i ] -= c;
            w[ i ][ i ] += c;
            w[ j ][ j ] += c;
        }
    }
    return res + 2 * max(w[ 0 ][ 1 ], w[ 0 ][ 2 ]);
}

// int main() {
//     int n, q;
//     cin >> n >> q;
//     string a, b;
//     cin >> a >> b;
//     init(a, b);
//     while(q--) {
//         int x, y;
//         cin >> x >> y;
//         cout << get_distance(x, y) << '\n'; 
//     }
// }

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