oj.uz

Submission #712613

# Submission time Handle Problem Language Result Execution time Memory
712613 2023-03-19T09:53:21 Z danikoynov Mutating DNA (IOI21_dna) C++17
100 / 100
 833 ms 8780 KB 
#include "dna.h"
#include <bits/stdc++.h>

using namespace std;


const int maxn = 1e5 + 10;

string s, t;
int pref[2][3][maxn];
int kf[3][3][maxn];
map < char, int > rev;
void init(std::string a, std::string b)
{
    s = a;
    t = b;
    rev['A'] = 0;
    rev['C'] = 1;
    rev['T'] = 2;
    for (int i = 0; i < a.size(); i ++)
    {
        if (i != 0)
        {
            for (int p = 0; p < 3; p ++)
                for (int k = 0; k < 2; k ++)
                    pref[k][p][i] = pref[k][p][i - 1];

            for (int p1 = 0; p1 < 3; p1 ++)
                for (int p2 = 0; p2 < 3; p2 ++)
                    kf[p1][p2][i] = kf[p1][p2][i - 1];
        }
        if (a[i] != b[i])
            kf[rev[a[i]]][rev[b[i]]][i] ++;
        pref[0][rev[a[i]]][i] ++;
        pref[1][rev[b[i]]][i] ++;
    }
}

int get_distance(int x, int y)
{


    string s1 = s.substr(x, y - x + 1);
    string t1 = t.substr(x, y - x + 1);
    int df[2][3], pf[3][3];
    for (int p = 0; p < 3; p ++)
    {
        df[0][p] = pref[0][p][y];
        df[1][p] = pref[1][p][y];
    }

    for (int p1 = 0; p1 < 3; p1 ++)
        for (int p2 = 0; p2 < 3; p2 ++)
            pf[p1][p2] = kf[p1][p2][y];

    if (x != 0)
    {
        for (int p = 0; p < 3; p ++)
        {
            df[0][p] -= pref[0][p][x - 1];
            df[1][p] -= pref[1][p][x - 1];
        }

        for (int p1 = 0; p1 < 3; p1 ++)
            for (int p2 = 0; p2 < 3; p2 ++)
                pf[p1][p2] -= kf[p1][p2][x - 1];

    }
    for (int p = 0; p < 3; p ++)
        if (df[0][p] != df[1][p])
            return -1;
    int ans = 0;
    for (int p1 = 0; p1 < 3; p1 ++)
        for (int p2 = 0; p2 < 3; p2 ++)
        {
            int mx = min(pf[p1][p2], pf[p2][p1]);
            ans += mx;
            pf[p1][p2] -= mx;
            pf[p2][p1] -= mx;
        }

    int add = 0;
    for (int p1 = 0; p1 < 3; p1 ++)
        for (int p2 = 0; p2 < 3; p2 ++)
            add += pf[p1][p2];
    ans = ans + (add / 3) * 2;
    return ans;
    /**for (int i = 0; i < t1.size(); i ++)
    {
        if (s1[i] == t1[i])
            continue;

        bool done = false;
        for (int j = i; j < t1.size(); j ++)
        {
            if (s1[j] == t1[i] && t1[j] == s1[i])
            {
                swap(s1[j], s1[i]);
                ans ++;
                done = true;
                break;
            }
        }

        if (!done)
        {
            for (int j = i; j < t1.size(); j ++)
            {
                if (s1[j] == t1[i] && s1[j] != t1[j])
                {
                    swap(s1[j], s1[i]);
                    ans ++;
                    done = true;
                    break;
                }
            }
        }
        ///cout << i << " : " << j << endl;
    }
    return ans;*/
}

Compilation message

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

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8176 KB Output is correct
2 Correct 42 ms 8244 KB Output is correct
3 Correct 61 ms 7704 KB Output is correct
4 Correct 56 ms 8268 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 9 ms 6820 KB Output is correct
5 Correct 8 ms 6836 KB Output is correct
6 Correct 8 ms 6868 KB Output is correct
7 Correct 8 ms 6484 KB Output is correct
8 Correct 9 ms 6924 KB Output is correct
9 Correct 7 ms 6868 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 9 ms 6820 KB Output is correct
5 Correct 8 ms 6836 KB Output is correct
6 Correct 8 ms 6868 KB Output is correct
7 Correct 8 ms 6484 KB Output is correct
8 Correct 9 ms 6924 KB Output is correct
9 Correct 7 ms 6868 KB Output is correct
10 Correct 58 ms 8224 KB Output is correct
11 Correct 47 ms 8260 KB Output is correct
12 Correct 375 ms 8296 KB Output is correct
13 Correct 368 ms 8428 KB Output is correct
14 Correct 429 ms 8724 KB Output is correct
15 Correct 378 ms 8608 KB Output is correct
16 Correct 403 ms 8292 KB Output is correct
17 Correct 420 ms 8484 KB Output is correct
18 Correct 458 ms 8760 KB Output is correct
19 Correct 718 ms 8208 KB Output is correct
20 Correct 716 ms 8396 KB Output is correct
21 Correct 833 ms 8632 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 9 ms 6820 KB Output is correct
5 Correct 8 ms 6836 KB Output is correct
6 Correct 8 ms 6868 KB Output is correct
7 Correct 8 ms 6484 KB Output is correct
8 Correct 9 ms 6924 KB Output is correct
9 Correct 7 ms 6868 KB Output is correct
10 Correct 6 ms 6356 KB Output is correct
11 Correct 8 ms 6840 KB Output is correct
12 Correct 9 ms 6484 KB Output is correct
13 Correct 8 ms 6900 KB Output is correct
14 Correct 8 ms 6868 KB Output is correct
15 Correct 9 ms 6924 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8176 KB Output is correct
2 Correct 42 ms 8244 KB Output is correct
3 Correct 61 ms 7704 KB Output is correct
4 Correct 56 ms 8268 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 216 KB Output is correct
11 Correct 9 ms 6820 KB Output is correct
12 Correct 8 ms 6836 KB Output is correct
13 Correct 8 ms 6868 KB Output is correct
14 Correct 8 ms 6484 KB Output is correct
15 Correct 9 ms 6924 KB Output is correct
16 Correct 7 ms 6868 KB Output is correct
17 Correct 58 ms 8224 KB Output is correct
18 Correct 47 ms 8260 KB Output is correct
19 Correct 375 ms 8296 KB Output is correct
20 Correct 368 ms 8428 KB Output is correct
21 Correct 429 ms 8724 KB Output is correct
22 Correct 378 ms 8608 KB Output is correct
23 Correct 403 ms 8292 KB Output is correct
24 Correct 420 ms 8484 KB Output is correct
25 Correct 458 ms 8760 KB Output is correct
26 Correct 718 ms 8208 KB Output is correct
27 Correct 716 ms 8396 KB Output is correct
28 Correct 833 ms 8632 KB Output is correct
29 Correct 6 ms 6356 KB Output is correct
30 Correct 8 ms 6840 KB Output is correct
31 Correct 9 ms 6484 KB Output is correct
32 Correct 8 ms 6900 KB Output is correct
33 Correct 8 ms 6868 KB Output is correct
34 Correct 9 ms 6924 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 49 ms 7756 KB Output is correct
37 Correct 45 ms 8244 KB Output is correct
38 Correct 372 ms 8372 KB Output is correct
39 Correct 375 ms 8780 KB Output is correct
40 Correct 424 ms 8692 KB Output is correct
41 Correct 6 ms 6868 KB Output is correct
42 Correct 428 ms 8416 KB Output is correct
43 Correct 415 ms 8720 KB Output is correct
44 Correct 455 ms 8712 KB Output is correct
45 Correct 691 ms 8284 KB Output is correct
46 Correct 737 ms 8628 KB Output is correct
47 Correct 824 ms 8632 KB Output is correct