Submission #576712

#	Time	Username	Problem	Language	Result	Execution time	Memory
576712		MohamedFaresNebili	Mutating DNA (IOI21_dna)	C++17	100 / 100	56 ms	11504 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
#include <ext/pb_ds/assoc_container.hpp>
 
        using namespace std;
        using namespace __gnu_pbds;
 
        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;
 
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        #define ub upper_bound
 
        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;
 
        int P[100001][3], Pr[100001][3];
        int M[100001][3], A[100001][3][3];
        string S, T; int N;
 
 
        void init(string a, string b) {
            S = a, T = b; N = S.length();
            vector<int> U, V;
 
            for(int l = 0; l < N; l++) {
                if(S[l] == 'A') U.pb(0);
                if(S[l] == 'C') U.pb(1);
                if(S[l] == 'T') U.pb(2);
 
                if(T[l] == 'A') V.pb(0);
                if(T[l] == 'C') V.pb(1);
                if(T[l] == 'T') V.pb(2);
            }
 
            for(int l = 0; l < N; l++) {
                P[l][U[l]]++; Pr[l][V[l]]++;
                M[l][U[l]] += (S[l] != T[l]);
                A[l][U[l]][V[l]]++;
                for(int i = 0; i < 3 && l > 0; i++) {
                    P[l][i] += P[l - 1][i];
                    Pr[l][i] += Pr[l - 1][i];
                    M[l][i] += M[l - 1][i];
                    for(int j = 0; j < 3; j++)
                        A[l][i][j] += A[l - 1][i][j];
                }
            }
        }
 
        int get_distance(int x, int y) {
            for(int l = 0; l < 3; l++) {
                int X = P[y][l], Y = Pr[y][l];
                if(x) X -= P[x - 1][l], Y -= Pr[x - 1][l];
                if(X != Y) return -1;
            }
            int best = 1e9 + 7;
            for(int l = 0; l < 3; l++) {
                int res = M[y][l];
                if(x) res -= M[x - 1][l];
 
                int X = (l + 1) % 3, Y = (l + 2) % 3;
 
                int U = M[y][X], V = M[y][Y];
                if(x) U -= M[x - 1][X], V -= M[x - 1][Y];
 
                int u = A[y][l][X], uu = A[y][X][l];
                if(x) u -= A[x - 1][l][X], uu -= A[x - 1][X][l];
 
                int v = A[y][l][Y], vv = A[y][Y][l];
                if(x) v -= A[x - 1][l][Y], vv -= A[x - 1][Y][l];
 
                U -= min(u, uu), V -= min(v, vv);
                
                res += min(U, V);
                best = min(best, res);
            }
            return best;
        }

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