Submission #437192

#	Time	Username	Problem	Language	Result	Execution time	Memory
437192		Bom164	Mutating DNA (IOI21_dna)	C++17	22 / 100	1579 ms	3276 KiB

dna

#include<bits/stdc++.h>
#include<iostream>

using namespace std;

#define ll              long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define mod             1000000007
#define inf             1e18
#define w(x)            int x; cin>>x; while(x--)

vector<int> as(111111);
vector<int> bs(111111);
string ad,bd;

void init(string a,string b){
    int n=a.size();
    ad=a;
    bd=b;
    for(int i=0;i<n;i++){
        if(a[i]=='A'){
            as[i]=0;
        }else if(a[i]=='C'){
            as[i]=1;
        }else if(a[i]=='T'){
            as[i]=2;
        }
    }
    for(int i=0;i<n;i++){
        if(b[i]=='A'){
            bs[i]=0;
        }else if(b[i]=='C'){
            bs[i]=1;
        }else if(b[i]=='T'){
            bs[i]=2;
        }
    }
    for(int i=1;i<=n-1;i++){
        as[i]+=as[i-1];
        bs[i]+=bs[i-1];
    }
}

int get_distance(int l,int r){
    int ac=as[r]-(l==0?0:as[l-1]);
    int bc=bs[r]-(l==0?0:bs[l-1]);
    int c=0;
    if(ac!=bc) return -1;
    for(int i=l;i<=r;i++){
        if(ad[i]!=bd[i]) c++;
    }
    return (c+1)/2;
}

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