Submission #1142146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142146		samiiovic	Mutating DNA (IOI21_dna)	C++20	0 / 100	19 ms	4608 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
#define REP(i, a, b) for(int i = a; i<b; i++)
#define all(v) v.begin(), v.end()
#define i64 long long
using namespace std;

int n=100000;
vector<int> aa(n, 0);
vector<int> ca(n, 0);
vector<int> ta(n, 0);
vector<int> ab(n, 0);
vector<int> cb(n, 0);
vector<int> tb(n, 0);

void init(string a, string b){
    if(a[0] == 'A') aa[0] = 1;
    else if(a[0] == 'C') ca[0] = 1;
    else if(a[0] == 'T') ta[0] = 1;

    if(b[0] == 'A') ab[0] = 1;
    else if(b[0] == 'C') cb[0] = 1;
    else if(b[0] == 'T') tb[0] = 1;

    REP(i, 1, n){
        if(a[i] == 'A') aa[i] += aa[i-1] + 1;
        else aa[i] = aa[i-1];
        if(a[i] == 'C') ca[i] += ca[i-1] + 1;
        else ca[i] = ca[i-1];
        if(a[i] == 'T') ta[i] += ta[i-1] + 1;
        else ta[i] = ta[i-1];

        if(b[i] == 'A') ab[i] += ab[i-1] + 1;
        else ab[i] = ab[i-1];
        if(b[i] == 'C') cb[i] += cb[i-1] + 1;
        else cb[i] = cb[i-1];
        if(b[i] == 'T') tb[i] += tb[i-1] + 1;
        else tb[i] = tb[i-1];
    }
    // REP(i, 0, n) cerr<<ta[i]<<" ";
    // cerr<<'\n';
    // REP(i, 0, n) cerr<<tb[i]<<" ";
    // cerr<<'\n';
    // REP(i, 0, n) cerr<<ca[i]<<" ";
    // cerr<<'\n';
    // REP(i, 0, n) cerr<<cb[i]<<" ";
    // cerr<<'\n';
    // REP(i, 0, n) cerr<<aa[i]<<" ";
    // cerr<<'\n';
    // REP(i, 0, n) cerr<<ab[i]<<" ";
    // cerr<<'\n';
}

int get_distance(int x, int y){

    if(x != 0){
        // cerr<<"ta[y] - tb[y]  "<<ta[y] - tb[y]<<'\n';
        // cerr<<"ta[x-1] - tb[x-1]  "<<ta[x-1] - tb[x-1]<<'\n';
        // cerr<<"aa[y] - ab[y]  "<<aa[y] - ab[y]<<'\n';
        // cerr<<"aa[x-1] - ab[x-1]  "<<aa[x-1] - ab[x-1]<<'\n';
        // cerr<<"ca[y] - cb[y]  "<<ca[y] - cb[y]<<'\n';
        // cerr<<"ca[x-1] - cb[x-1]  "<<ca[x-1] - cb[x-1]<<'\n';
        if((abs(ta[y] - tb[y]) == abs(ta[x-1] - tb[x-1])) && (abs(aa[y] - ab[y]) == abs(aa[x-1] - ab[x-1])) && (abs(ca[y] - cb[y]) == abs(ca[x-1] - cb[x-1]))){
            int cnt = 0;
            REP(i, x, y){
                if(ta[i]-ta[x-(i+1)] != tb[i]-tb[x-(i+1)]) cnt++;
                //else cnt--;
                if(ca[i]-ca[x-(i+1)] != cb[i]-cb[x-(i+1)]) cnt++;
                //else cnt--;
                if(aa[i]-aa[x-(i+1)] != ab[i]-ab[x-(i+1)]) cnt++;
                //else cnt--;
            }
            // cerr<<cnt<<'\n';
            // int ans;
            // if(cnt%2 == 0 && cnt != 0) ans = cnt/2;
            // else if(cnt != 0) ans = (cnt+1)/2;
            // else ans = 1;
            // return ans;
            //cerr<<cnt<<'\n';
            int ans;
            int size = y - x;
            if(size == 2) ans = 2;
            else if(size%2 == 0) ans = size/2;
            else ans = 1 + size/2;
            return ans;
        } else{
            //cerr<<12344444<<'\n';
            return -1;
        }
    } else if(x==0){
        if((abs(ta[y]) == abs(tb[y] )) && (abs(aa[y] ) == abs(ab[y])) && (abs(ca[y])== abs(cb[y]))){
            int cnt = 0;       
            if(ta[0] != tb[0]) cnt++;
            if(ca[0] != cb[0]) cnt++;
            if(aa[0] != ab[0]) cnt++;
            REP(i, x+1, y){
                if(ta[i]-ta[x-(i+1)] != tb[i]-tb[x-(i+1)]) cnt++;
                //else cnt--;
                if(ca[i]-ca[x-(i+1)] != cb[i]-cb[x-(i+1)]) cnt++;
                // else cnt--;
                if(aa[i]-aa[x-(i+1)] != ab[i]-ab[x-(i+1)]) cnt++;
                // else cnt--;
            }
            //cerr<<cnt<<'\n';
            int ans;
            int size = y - x;
            if(size == 2) ans = 2;
            else if(size%2 == 0) ans = size/2;
            else ans = 1 + size/2;
            return ans;
        } else{
            //cerr<<12344444<<'\n';
            return -1;
        }
    }
    return -1;
}

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