oj.uz

Submission #437192

# Submission time Handle Problem Language Result Execution time Memory
437192 2021-06-26T03:07:16 Z Bom164 Mutating DNA (IOI21_dna) C++17
22 / 100
 1500 ms 3276 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);
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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3268 KB Output is correct
2 Correct 41 ms 3276 KB Output is correct
3 Incorrect 42 ms 3204 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 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 4 ms 1868 KB Output is correct
5 Correct 4 ms 1868 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct
7 Correct 6 ms 1868 KB Output is correct
8 Correct 6 ms 1868 KB Output is correct
9 Correct 4 ms 1868 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 4 ms 1868 KB Output is correct
5 Correct 4 ms 1868 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct
7 Correct 6 ms 1868 KB Output is correct
8 Correct 6 ms 1868 KB Output is correct
9 Correct 4 ms 1868 KB Output is correct
10 Correct 41 ms 3236 KB Output is correct
11 Correct 39 ms 3268 KB Output is correct
12 Execution timed out 1579 ms 3012 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 4 ms 1868 KB Output is correct
5 Correct 4 ms 1868 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct
7 Correct 6 ms 1868 KB Output is correct
8 Correct 6 ms 1868 KB Output is correct
9 Correct 4 ms 1868 KB Output is correct
10 Incorrect 6 ms 1868 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 39 ms 3268 KB Output is correct
2 Correct 41 ms 3276 KB Output is correct
3 Incorrect 42 ms 3204 KB Output isn't correct
4 Halted 0 ms 0 KB -