oj.uz

Submission #853137

# Submission time Handle Problem Language Result Execution time Memory
853137 2023-09-23T13:15:14 Z onepunchac168 Mutating DNA (IOI21_dna) C++17
100 / 100
 41 ms 11128 KB 
//------------------------------------\\
//   ------------------------------   \\
//  |  created by Dinh Manh Hung   |  \\
//  |      tht.onepunchac168       |  \\
//  |     THPT CHUYEN HA TINH      |  \\
//  |      HA TINH, VIET NAM       |  \\
//  |           Siuuu              |  \\
//   ------------------------------   \\
//------------------------------------\\

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

#define            task     ""
#define       file(name)    if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define             ldb     long double
#define              pb     push_back
#define              eb     emplace_back
#define              fi     first
#define              se     second
#define           all(x)    begin(x),end(x)
#define       uniquev(v)    v.resize(unique(all(v))-v.begin())
#define       rep(i,a,b)    for (int i=a;i<=b;i++)
#define        cntbit(v)    __builtin_popcountll(v)
#define         gcd(a,b)    __gcd(a,b)
#define         lcm(a,b)    ((1LL*a*b)/__gcd(a,b))
#define          mask(x)    (1LL<<(x))
#define     readbit(x,i)    ((x>>i)&1)
#define             Yes     cout << "Yes"
#define             YES     cout << "YES"
#define              No     cout << "No"
#define              NO     cout << "NO"

typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const ll mod=1e9+7;
const char nl = '\n';

inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = (xo<<1) + (xo<<3) + co - '0';
    return xo;
}

void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}

// DEBUG

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


/* END OF TEMPLATE*/

// ================= Solution =================//

const int N=1e5+5;
ll n;
ll dp[N][3][3];
ll solve(char aa)
{
    if (aa=='A')
    {
        return 0;
    }
    if (aa=='T')
    {
        return 1;
    }
    return 2;
}
void init(std::string a, std::string b) {
    n=a.size();
    a=" "+a;
    b=" "+b;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=2;j++)
        {
            for (int h=0;h<=2;h++)
            {
                dp[i][j][h]+=dp[i-1][j][h];
            }
        }
        dp[i][solve(a[i])][solve(b[i])]++;
    }
}
ll s[3][3];
ll d[3][2];
int get_distance(int x, int y) {
    x++;
    y++;
    for (int i=0;i<=2;i++)
    {
        for (int j=0;j<=1;j++)
        {
            d[i][j]=0;
        }
    }
    for (int i=0;i<=2;i++)
    {
        for (int j=0;j<=2;j++)
        {
            s[i][j]=dp[y][i][j]-dp[x-1][i][j];
            d[i][0]+=s[i][j];
            d[j][1]+=s[i][j];
            if (i==j)
            {
                s[i][j]=0;
            }
        }
    }
    for (int i=0;i<=2;i++)
    {
        if (d[i][0]!=d[i][1])
        {
            return -1;
        }
    }
    int dem=0;
    for (int i=0;i<=2;i++)
    {
        for (int j=0;j<=2;j++)
        {
            ll pp=min(s[i][j],s[j][i]);
            s[i][j]-=pp;
            s[j][i]-=pp;
            dem+=pp;
        }
    }
    ll gmax=0;
    for (int i=0;i<=2;i++)
    {
        for (int j=0;j<=2;j++)
        {
            if (s[i][j]!=0)
            {
                gmax=s[i][j];
            }
        }
    }
    dem+=gmax*2;
	return dem;
}
/*
void onepunchac168();

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    file(task);
    int tests;
    tests=1;
    //cin>>tests;
    while (tests--)
    {
        onepunchac168();
    }
}

const int N=2e5+5;

void onepunchac168()
{

}
*/

// goodbye see ya

Compilation message

dna.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\\
      | ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10580 KB Output is correct
2 Correct 30 ms 10596 KB Output is correct
3 Correct 29 ms 9940 KB Output is correct
4 Correct 30 ms 10668 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 8120 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8252 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 4 ms 8136 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 8120 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8252 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 4 ms 8136 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct
10 Correct 32 ms 10516 KB Output is correct
11 Correct 29 ms 10672 KB Output is correct
12 Correct 30 ms 10384 KB Output is correct
13 Correct 31 ms 10472 KB Output is correct
14 Correct 36 ms 11032 KB Output is correct
15 Correct 29 ms 10944 KB Output is correct
16 Correct 30 ms 10296 KB Output is correct
17 Correct 29 ms 10460 KB Output is correct
18 Correct 30 ms 10960 KB Output is correct
19 Correct 30 ms 10432 KB Output is correct
20 Correct 28 ms 10432 KB Output is correct
21 Correct 28 ms 10932 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 8120 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8252 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 4 ms 8136 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct
10 Correct 3 ms 7512 KB Output is correct
11 Correct 3 ms 8284 KB Output is correct
12 Correct 3 ms 7772 KB Output is correct
13 Correct 3 ms 8284 KB Output is correct
14 Correct 4 ms 8168 KB Output is correct
15 Correct 4 ms 8284 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10580 KB Output is correct
2 Correct 30 ms 10596 KB Output is correct
3 Correct 29 ms 9940 KB Output is correct
4 Correct 30 ms 10668 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 8120 KB Output is correct
12 Correct 3 ms 8284 KB Output is correct
13 Correct 4 ms 8252 KB Output is correct
14 Correct 3 ms 7772 KB Output is correct
15 Correct 4 ms 8136 KB Output is correct
16 Correct 3 ms 8284 KB Output is correct
17 Correct 32 ms 10516 KB Output is correct
18 Correct 29 ms 10672 KB Output is correct
19 Correct 30 ms 10384 KB Output is correct
20 Correct 31 ms 10472 KB Output is correct
21 Correct 36 ms 11032 KB Output is correct
22 Correct 29 ms 10944 KB Output is correct
23 Correct 30 ms 10296 KB Output is correct
24 Correct 29 ms 10460 KB Output is correct
25 Correct 30 ms 10960 KB Output is correct
26 Correct 30 ms 10432 KB Output is correct
27 Correct 28 ms 10432 KB Output is correct
28 Correct 28 ms 10932 KB Output is correct
29 Correct 3 ms 7512 KB Output is correct
30 Correct 3 ms 8284 KB Output is correct
31 Correct 3 ms 7772 KB Output is correct
32 Correct 3 ms 8284 KB Output is correct
33 Correct 4 ms 8168 KB Output is correct
34 Correct 4 ms 8284 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 28 ms 9932 KB Output is correct
37 Correct 30 ms 10672 KB Output is correct
38 Correct 29 ms 10440 KB Output is correct
39 Correct 29 ms 10936 KB Output is correct
40 Correct 30 ms 10924 KB Output is correct
41 Correct 3 ms 8284 KB Output is correct
42 Correct 30 ms 10388 KB Output is correct
43 Correct 34 ms 10872 KB Output is correct
44 Correct 29 ms 11128 KB Output is correct
45 Correct 30 ms 10428 KB Output is correct
46 Correct 29 ms 10868 KB Output is correct
47 Correct 29 ms 10928 KB Output is correct