Submission #832114

#	Time	Username	Problem	Language	Result	Execution time	Memory
832114		minhcool	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	9676 KiB

dna

//#define local
#ifndef local
#include "dna.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, pref1[N][3], pref2[N][3], pref3[N][3][3];

char c[] = {'C', 'A', 'T'};

void init(string a, string b) {
    n = a.length();
    a = '*' + a, b = '*' + b;
    //cout << "OK\n";
    //cout << a.length() << " " << b.length() << "\n";
    //return;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++){
            pref1[i][j] = pref1[i - 1][j] + (a[i] == c[j]);
            pref2[i][j] = pref2[i - 1][j] + (b[i] == c[j]);
            for(int k = 0; k < 3; k++){
                pref3[i][j][k] = pref3[i - 1][j][k] + (a[i] == c[j] && b[i] == c[k]);
            }
        }
    }
}

int get_distance(int x, int y) {
    //return 0;
    x++, y++;
    for(int i = 0; i < 3; i++) if((pref1[y][i] - pref1[x - 1][i]) != (pref2[y][i] - pref2[x - 1][i])) return -1;
    int ca = (pref3[y][0][1] - pref3[x - 1][0][1]);
    int ct = (pref3[y][0][2] - pref3[x - 1][0][2]);
    int ac = (pref3[y][1][0] - pref3[x - 1][1][0]);
    int at = (pref3[y][1][2] - pref3[x - 1][1][2]);
    int tc = (pref3[y][2][0] - pref3[x - 1][2][0]);
    int ta = (pref3[y][2][1] - pref3[x - 1][2][1]);
    int answer = 0;
    int temp = min(ac, ca);
    ac -= temp, ca -= temp; answer += temp;
    temp = min(at, ta);
    at -= temp, ta -= temp, answer += temp;
    temp = min(ct, tc);
    ct -= temp, tc -= temp, answer += temp;
    //cout << ac << " " << ct << " " << ta << "\n";
    //cout << ca << " " << at << " " << tc << "\n";
    //assert(ac == ct && ct == ta);
    answer += ac * 2;
    //assert(ca == at && at == tc);
    answer += ca * 2;
    return answer;
	//return 0;
}

#ifdef local
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    process();
}
#endif

Compilation message (stderr)

dna.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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