oj.uz

Submission #437201

# Submission time Handle Problem Language Result Execution time Memory
437201 2021-06-26T03:29:40 Z Bom164 Mutating DNA (IOI21_dna) C++17
35 / 100
 51 ms 4056 KB 
#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);
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];
    }
    for(int i=0;i<n;i++){
        if(a[i]!=b[i]){
            dif[i]=1;
        }
    }
    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+1)/2;
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3652 KB Output is correct
2 Correct 51 ms 3680 KB Output is correct
3 Incorrect 45 ms 3760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 5 ms 2380 KB Output is correct
5 Correct 5 ms 2380 KB Output is correct
6 Correct 6 ms 2424 KB Output is correct
7 Correct 5 ms 2252 KB Output is correct
8 Correct 5 ms 2380 KB Output is correct
9 Correct 5 ms 2380 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 5 ms 2380 KB Output is correct
5 Correct 5 ms 2380 KB Output is correct
6 Correct 6 ms 2424 KB Output is correct
7 Correct 5 ms 2252 KB Output is correct
8 Correct 5 ms 2380 KB Output is correct
9 Correct 5 ms 2380 KB Output is correct
10 Correct 43 ms 3660 KB Output is correct
11 Correct 49 ms 3676 KB Output is correct
12 Correct 39 ms 3892 KB Output is correct
13 Correct 40 ms 4044 KB Output is correct
14 Correct 41 ms 4044 KB Output is correct
15 Correct 38 ms 4036 KB Output is correct
16 Correct 37 ms 4024 KB Output is correct
17 Correct 37 ms 3948 KB Output is correct
18 Correct 37 ms 4056 KB Output is correct
19 Correct 36 ms 4032 KB Output is correct
20 Correct 37 ms 4044 KB Output is correct
21 Correct 38 ms 4036 KB Output is correct

Subtask #4
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 5 ms 2380 KB Output is correct
5 Correct 5 ms 2380 KB Output is correct
6 Correct 6 ms 2424 KB Output is correct
7 Correct 5 ms 2252 KB Output is correct
8 Correct 5 ms 2380 KB Output is correct
9 Correct 5 ms 2380 KB Output is correct
10 Incorrect 6 ms 2252 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3652 KB Output is correct
2 Correct 51 ms 3680 KB Output is correct
3 Incorrect 45 ms 3760 KB Output isn't correct
4 Halted 0 ms 0 KB -