Submission #672018

#	Time	Username	Problem	Language	Result	Execution time	Memory
672018		tbzard	Mutating DNA (IOI21_dna)	C++17	100 / 100	44 ms	8584 KiB

dna

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

const char c[3] = {'A', 'C', 'T'};
int idx[500];
int idx2[5][5];
int sum[100005][9];
int sumA[100005][3];
int sumB[100005][3];

void init(string a, string b){
    for(int i=0;i<3;i++){
        idx[c[i]] = i;
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            idx2[idx[c[i]]][idx[c[j]]] = i*3 + j;
        }
    }
    int n = a.length();
    for(int i=1;i<=n;i++){
        int c1 = idx[a[i-1]];
        int c2 = idx[b[i-1]];
        sumA[i][c1] = 1;
        sumB[i][c2] = 1;
        for(int j=0;j<3;j++){
            sumA[i][j] += sumA[i-1][j];
            sumB[i][j] += sumB[i-1][j];
        }

        sum[i][idx2[c1][c2]] = 1;
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                sum[i][idx2[j][k]] += sum[i-1][idx2[j][k]];
            }
        }
    }
}

int get_distance(int x, int y){
    x++, y++;
    int ans = 0, cnt = 0;
    for(int j=0;j<3;j++){
        if(sumA[y][j] - sumA[x-1][j] != sumB[y][j] - sumB[x-1][j]) return -1;
        cnt += sum[y][idx2[j][j]] - sum[x-1][idx2[j][j]];
    }
    for(int j=0;j<3;j++){
        for(int k=j+1;k<3;k++){
            ans += min(sum[y][idx2[j][k]]-sum[x-1][idx2[j][k]], sum[y][idx2[k][j]]-sum[x-1][idx2[k][j]]);
            cnt += min(sum[y][idx2[j][k]]-sum[x-1][idx2[j][k]], sum[y][idx2[k][j]]-sum[x-1][idx2[k][j]])*2;
        }
    }
    ans += (y-x+1 - cnt)/3 * 2;
    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:26:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         idx[c[i]] = i;
      |             ~~~^
dna.cpp:30:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |             idx2[idx[c[i]]][idx[c[j]]] = i*3 + j;
      |                      ~~~^
dna.cpp:30:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |             idx2[idx[c[i]]][idx[c[j]]] = i*3 + j;
      |                                 ~~~^
dna.cpp:35:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |         int c1 = idx[a[i-1]];
      |                            ^
dna.cpp:36:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   36 |         int c2 = idx[b[i-1]];
      |                            ^

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