oj.uz

Submission #437195

# Submission time Handle Problem Language Result Execution time Memory
437195 2021-06-26T03:14:52 Z Bom164 Mutating DNA (IOI21_dna) C++17
22 / 100
 1500 ms 3372 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]=3;
        }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]=3;
        }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 40 ms 3236 KB Output is correct
2 Correct 37 ms 3240 KB Output is correct
3 Incorrect 43 ms 3192 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 4 ms 1944 KB Output is correct
7 Correct 6 ms 1868 KB Output is correct
8 Correct 6 ms 1956 KB Output is correct
9 Correct 5 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 4 ms 1944 KB Output is correct
7 Correct 6 ms 1868 KB Output is correct
8 Correct 6 ms 1956 KB Output is correct
9 Correct 5 ms 1868 KB Output is correct
10 Correct 44 ms 3268 KB Output is correct
11 Correct 51 ms 3372 KB Output is correct
12 Execution timed out 1550 ms 2944 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 4 ms 1944 KB Output is correct
7 Correct 6 ms 1868 KB Output is correct
8 Correct 6 ms 1956 KB Output is correct
9 Correct 5 ms 1868 KB Output is correct
10 Incorrect 5 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 40 ms 3236 KB Output is correct
2 Correct 37 ms 3240 KB Output is correct
3 Incorrect 43 ms 3192 KB Output isn't correct
4 Halted 0 ms 0 KB -