Submission #1001521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001521		vjudge1	Mutating DNA (IOI21_dna)	C++17	21 / 100	20 ms	6328 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
#pragma GCC optimize("-O3")
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pb push_back
#define p_b pop_back
using namespace std;
const ll sz = 1e5+5;
ll cnt[3][sz], cnt2[3][sz], pref[sz], i, n;
void init(string a, string b) {
    a = '#' + a;
    b = '#' + b;
    n = a.size();
    for(i = 1; i <= n; i++)
        pref[i] = pref[i-1] + (a[i] != b[i]);
    for(i = 1; i <= n; i++)
    {
        cnt[0][i] = cnt[0][i-1];
        cnt[1][i] = cnt[1][i-1];
        cnt[2][i] = cnt[2][i-1];
        cnt2[0][i] = cnt2[0][i-1];
        cnt2[1][i] = cnt2[1][i-1];
        cnt2[2][i] = cnt2[2][i-1];
        if(a[i] == 'A')
            cnt[0][i] = cnt[0][i-1] + 1;
        if(a[i] == 'C')
            cnt[1][i] = cnt[1][i-1] + 1;
        if(a[i] == 'T')
            cnt[2][i] = cnt[2][i-1] + 1;
        if(b[i] == 'A')
            cnt2[0][i] = cnt2[0][i-1] + 1;
        if(b[i] == 'C')
            cnt2[1][i] = cnt2[1][i-1] + 1;
        if(b[i] == 'T')
            cnt2[2][i] = cnt2[2][i-1] + 1;
    }
}

int get_distance(int x, int y) {
	x++, y++;
	ll acnt1 = cnt[0][y] - cnt[0][x-1];
	ll ccnt1 = cnt[1][y] - cnt[1][x-1];
	ll tcnt1 = cnt[2][y] - cnt[2][x-1];
	ll acnt2 = cnt2[0][y] - cnt2[0][x-1];
	ll ccnt2 = cnt2[1][y] - cnt2[1][x-1];
	ll tcnt2 = cnt2[2][y] - cnt2[2][x-1];
	//cout << acnt1 << ' ' << ccnt1 << ' ' << tcnt1 << ' ' << acnt2 << ' ' << ccnt2 << ' ' << tcnt2 << "\n";
	if(acnt1 != acnt2 || ccnt1 != ccnt2 || tcnt1 != tcnt2)
        return -1;
    return max(0, pref[y] - pref[x-1] - 1);
}
/*
int main()
{
    string a, b;
    cin >> a >> b;
    init(a, b);
    ll q;
    cin >> q;
    while(q--)
    {
        int x, y;
        cin >> x >> y;
        cout << get_distance(x, y) << "\n";
    }
}
*/

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