Submission #1008599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008599		nisanduu	Mutating DNA (IOI21_dna)	C++17	56 / 100	78 ms	53588 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);

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=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;
    }
    c = arr[y];
    if(x!=0) c -= arr[x-1];

    int ans = (c+1)/2;
    return ans;
    
}


// int main()
// {
//     init("ATACAT", "ACTATA");
//     cout<<get_distance(4, 5)<<endl;
    
//     return 0;
// }

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