Submission #437206

#	Time	Username	Problem	Language	Result	Execution time	Memory
437206		Bom164	Mutating DNA (IOI21_dna)	C++17	0 / 100	41 ms	4164 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);
vector<int> dif(111111,0);
string ad,bd;
int c=0;

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];
    }
    for(int i=0;i<n;i++){
        if(a[i]!=b[i]){
            dif[i]=1;
        }
    }
    for(int i=0;i<n;i++){
        if(dif[i]==1 && dif[i+1]==1 && dif[i+2]==1){
            c++;
            i+=2;
        }else if(dif[i]==1 && dif[i+1]==1){
            c++;
            i++;
        }
    }
    for(int i=1;i<=n-1;i++){
        dif[i]+=dif[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]);
    if(ac!=bc) return -1;
    int cd=dif[r]-(l==0?0:dif[l-1]);
    return cd-c;
}

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