oj.uz

Submission #594030

# Submission time Handle Problem Language Result Execution time Memory
594030 2022-07-11T22:57:13 Z rc_catunta Mutating DNA (IOI21_dna) C++17
100 / 100
 61 ms 9016 KB 
#include "dna.h"
#include <algorithm>
#include <vector>
#include <set>
#include <iostream>
using namespace std;

string sa, sb, a, b;
vector<int> A1,A2,T1,T2,C1,C2;
vector<int> AC, AT, CA, CT, TA, TC;

void init(string a, string b) {
	sa = a;
	sb = b;
	// Construimos la tabla de acumuladas
	A1.assign(a.size(),0);
	T1.assign(a.size(),0);
    C1.assign(a.size(),0);
	A2.assign(a.size(),0);
	T2.assign(a.size(),0);
    C2.assign(a.size(),0);
    AC.assign(a.size(),0);
    AT.assign(a.size(),0);
    CT.assign(a.size(),0);
    CA.assign(a.size(),0);
    TA.assign(a.size(),0);
    TC.assign(a.size(),0);
	for(int i=0;i<a.size();i++){
        if(a[i]=='A') A1[i]++;
        if(a[i]=='C') C1[i]++; 
        if(a[i]=='T') T1[i]++;
        if(b[i]=='A') A2[i]++; 
        if(b[i]=='C') C2[i]++;
        if(b[i]=='T') T2[i]++; 
        if(a[i]=='A' and b[i]=='C') AC[i]++;
        if(a[i]=='A' and b[i]=='T') AT[i]++;
        if(a[i]=='C' and b[i]=='T') CT[i]++;
        if(a[i]=='C' and b[i]=='A') CA[i]++;
        if(a[i]=='T' and b[i]=='A') TA[i]++;
        if(a[i]=='T' and b[i]=='C') TC[i]++;
        if(i>0){
            A1[i] += A1[i-1];
            A2[i] += A2[i-1];
            C1[i] += C1[i-1];
            C2[i] += C2[i-1];
            T1[i] += T1[i-1];
            T2[i] += T2[i-1];
            AC[i] += AC[i-1];
            AT[i] += AT[i-1];
            CT[i] += CT[i-1];
            CA[i] += CA[i-1];
            TA[i] += TA[i-1];
            TC[i] += TC[i-1];
        }
	}
}

int get_distance(int x, int y) {
    int res = 0;
    int ca1 = A1[y];
    int cc1 = C1[y];
    int ct1 = T1[y];
    int ca2 = A2[y];
    int cc2 = C2[y];
    int ct2 = T2[y];
    if(x>0){
        ca1 -= A1[x-1];
        cc1 -= C1[x-1];
        ct1 -= T1[x-1];
        ca2 -= A2[x-1];
        cc2 -= C2[x-1];
        ct2 -= T2[x-1];
    }
    if(ca1 == ca2 and cc1 == cc2 and ct1 == ct2){
        // Se puede
        int cac = AC[y];
        int cat = AT[y];
        int cct = CT[y];
        int cca = CA[y];
        int cta = TA[y];
        int ctc = TC[y];
        if(x>0){
            cac -= AC[x-1];
            cat -= AT[x-1];
            cct -= CT[x-1];
            cca -= CA[x-1];
            cta -= TA[x-1];
            ctc -= TC[x-1];   
        }   
        //cout<<cac<<" "<<cat<<" "<<cct<<" "<<cca<<" "<<cta<<" "<<ctc<<"\n";
        // AC con CA
        int mini = min(cac,cca);
        res += mini;
        cac -= mini;
        cca -= mini;
        // AT con TA
        mini = min(cat,cta);
        res += mini;
        cat -= mini;
        cta -= mini;

        mini = min(cct,ctc);
        res += mini;
        cct -= mini;
        ctc -= mini;
        int cmdif = ((cac + cca +cat + cta + cct + ctc)/3)*2;
        res += cmdif;
        return res;
    }
    else return -1;
}

Compilation message

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<a.size();i++){
      |              ~^~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7104 KB Output is correct
2 Correct 48 ms 8484 KB Output is correct
3 Correct 57 ms 8000 KB Output is correct
4 Correct 46 ms 8500 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 300 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 15 ms 5844 KB Output is correct
5 Correct 16 ms 5980 KB Output is correct
6 Correct 15 ms 5844 KB Output is correct
7 Correct 17 ms 5532 KB Output is correct
8 Correct 18 ms 5972 KB Output is correct
9 Correct 16 ms 5944 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 15 ms 5844 KB Output is correct
5 Correct 16 ms 5980 KB Output is correct
6 Correct 15 ms 5844 KB Output is correct
7 Correct 17 ms 5532 KB Output is correct
8 Correct 18 ms 5972 KB Output is correct
9 Correct 16 ms 5944 KB Output is correct
10 Correct 46 ms 8364 KB Output is correct
11 Correct 51 ms 8404 KB Output is correct
12 Correct 47 ms 8388 KB Output is correct
13 Correct 57 ms 8536 KB Output is correct
14 Correct 47 ms 9016 KB Output is correct
15 Correct 44 ms 8692 KB Output is correct
16 Correct 43 ms 8320 KB Output is correct
17 Correct 43 ms 8472 KB Output is correct
18 Correct 46 ms 8784 KB Output is correct
19 Correct 48 ms 8280 KB Output is correct
20 Correct 42 ms 8612 KB Output is correct
21 Correct 42 ms 8704 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 15 ms 5844 KB Output is correct
5 Correct 16 ms 5980 KB Output is correct
6 Correct 15 ms 5844 KB Output is correct
7 Correct 17 ms 5532 KB Output is correct
8 Correct 18 ms 5972 KB Output is correct
9 Correct 16 ms 5944 KB Output is correct
10 Correct 17 ms 5488 KB Output is correct
11 Correct 17 ms 6012 KB Output is correct
12 Correct 15 ms 5664 KB Output is correct
13 Correct 16 ms 6012 KB Output is correct
14 Correct 17 ms 5972 KB Output is correct
15 Correct 16 ms 5972 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7104 KB Output is correct
2 Correct 48 ms 8484 KB Output is correct
3 Correct 57 ms 8000 KB Output is correct
4 Correct 46 ms 8500 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 15 ms 5844 KB Output is correct
12 Correct 16 ms 5980 KB Output is correct
13 Correct 15 ms 5844 KB Output is correct
14 Correct 17 ms 5532 KB Output is correct
15 Correct 18 ms 5972 KB Output is correct
16 Correct 16 ms 5944 KB Output is correct
17 Correct 46 ms 8364 KB Output is correct
18 Correct 51 ms 8404 KB Output is correct
19 Correct 47 ms 8388 KB Output is correct
20 Correct 57 ms 8536 KB Output is correct
21 Correct 47 ms 9016 KB Output is correct
22 Correct 44 ms 8692 KB Output is correct
23 Correct 43 ms 8320 KB Output is correct
24 Correct 43 ms 8472 KB Output is correct
25 Correct 46 ms 8784 KB Output is correct
26 Correct 48 ms 8280 KB Output is correct
27 Correct 42 ms 8612 KB Output is correct
28 Correct 42 ms 8704 KB Output is correct
29 Correct 17 ms 5488 KB Output is correct
30 Correct 17 ms 6012 KB Output is correct
31 Correct 15 ms 5664 KB Output is correct
32 Correct 16 ms 6012 KB Output is correct
33 Correct 17 ms 5972 KB Output is correct
34 Correct 16 ms 5972 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 43 ms 7948 KB Output is correct
37 Correct 48 ms 8488 KB Output is correct
38 Correct 61 ms 8472 KB Output is correct
39 Correct 47 ms 8808 KB Output is correct
40 Correct 45 ms 8760 KB Output is correct
41 Correct 18 ms 5944 KB Output is correct
42 Correct 45 ms 8352 KB Output is correct
43 Correct 49 ms 8736 KB Output is correct
44 Correct 47 ms 8780 KB Output is correct
45 Correct 42 ms 8344 KB Output is correct
46 Correct 42 ms 8716 KB Output is correct
47 Correct 43 ms 8724 KB Output is correct