Submission #1010403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010403		nisanduu	Mutating DNA (IOI21_dna)	C++17	100 / 100	91 ms	58408 KiB

dna

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N = 1e5 + 10;
string st1,st2;
vector<vector<ll>> v(N,vector<ll>(26)),v1(N,vector<ll>(26));
vector<ll> arr(N);
vector<ll> AC(N),CA(N),AT(N),TA(N),CT(N),TC(N);
void init(string a,string b){
    st1=a;
    st2=b;
    ll n = a.length();
    
    for(ll i=0;i<n;i++){
        int x = a[i]-'A';
        v[i][x]=1;
    }
    for(ll i=0;i<n;i++){
        int x = b[i]-'A';
        v1[i][x]=1;
    }
    for(ll i=0;i<n;i++){
        if(a[i]==b[i]) continue;
        if(a[i]=='A'){
            if(b[i]=='C') AC[i]++;
            else AT[i]++;
        }else if(a[i]=='C'){
            if(b[i]=='A') CA[i]++;
            else CT[i]++;
        }else{
            if(b[i]=='A') TA[i]++;
            else TC[i]++;
        }
    }
    for(ll i=1;i<n;i++) AC[i] = AC[i] + AC[i-1];
    for(ll i=1;i<n;i++) AT[i] = AT[i] + AT[i-1];
    for(ll i=1;i<n;i++) CA[i] = CA[i] + CA[i-1];
    for(ll i=1;i<n;i++) CT[i] = CT[i] + CT[i-1];
    for(ll i=1;i<n;i++) TA[i] = TA[i] + TA[i-1];
    for(ll i=1;i<n;i++) TC[i] = TC[i] + TC[i-1];
    for(ll i=1;i<n;i++){
        for(ll j=0;j<26;j++){
            v[i][j] = v[i-1][j] + v[i][j];
            v1[i][j] = v1[i-1][j] + v1[i][j];
        }
    }
    for(ll i=0;i<n;i++){
        arr[i] = (a[i]!=b[i]);
    }
    for(ll i=1;i<n;i++){
        arr[i] += arr[i-1];
    }
}
map<int,map<int,int>> mp;
int get_distance(int x,int y){
    int c = 0;
    for(ll i=0;i<26;i++){
        ll am1 = v[y][i];
        ll am2 = v1[y][i];
        if(x!=0) {
            am1 -= v[x-1][i];
            am2 -= v1[x-1][i];
        }
        if(am1!=am2) return -1;
    }
    int ans = 0;
    ll ACc = AC[y],ATc = AT[y],CTc = CT[y],CAc = CA[y],TAc = TA[y],TCc = TC[y];
    if(x!=0){
        ACc -= AC[x-1];
        ATc -= AT[x-1];
        CTc -= CT[x-1];
        CAc -= CA[x-1];
        TAc -= TA[x-1];
        TCc -= TC[x-1];
    }
    ans += min(ACc,CAc);
    ans += min(ATc,TAc);
    ans += min(CTc,TCc);
    ll cn = (ACc + CAc) - 2*min(ACc,CAc) + (ATc + TAc) - 2*min(ATc,TAc) + (CTc + TCc) - 2*min(CTc,TCc);
    ans += ((cn / 3)*2);
    return ans;
    
}


// int main()
// {
//     init("ATC", "ACT");
//     cout<<get_distance(0, 2)<<endl;
    
//     return 0;
// }

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:64:9: warning: unused variable 'c' [-Wunused-variable]
   64 |     int c = 0;
      |         ^

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