# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
861259 |
2023-10-15T18:11:25 Z |
midi |
Mutating DNA (IOI21_dna) |
C++17 |
|
40 ms |
13592 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define float long double
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef unordered_map<ll,ll> umapll;
#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define allrev(x) (x).rbegin(), (x).rend()
#define in(s,x) ((s).find((x)) != (s).end())
#define mxN 100'010ll
#define INF (LLONG_MAX>>2ll)
#define MOD 1'000'000'007ll
inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }
ll n;
vc<char> a(mxN), b(mxN);
vcll aca(mxN, 0), caa(mxN, 0), ata(mxN, 0), taa(mxN, 0), cta(mxN, 0), tca(mxN, 0);
vcll cntaa(mxN, 0), cntca(mxN, 0), cntta(mxN, 0);
vcll cntab(mxN, 0), cntcb(mxN, 0), cnttb(mxN, 0);
inline void build_pcas ()
{
ll i;
f0r(i,1,n)
{
a[i]+=32;
b[i]+=32;
}
f0r(i,1,n)
{
char c1=a[i], c2=b[i];
cntaa[i] = cntaa[i-1] + (c1=='a');
cntab[i] = cntab[i-1] + (c2=='a');
cntca[i] = cntca[i-1] + (c1=='c');
cntcb[i] = cntcb[i-1] + (c2=='c');
cntta[i] = cntta[i-1] + (c1=='t');
cnttb[i] = cnttb[i-1] + (c2=='t');
aca[i] = aca[i-1] + (c1=='a' && c2=='c');
caa[i] = caa[i-1] + (c1=='c' && c2=='a');
ata[i] = ata[i-1] + (c1=='a' && c2=='t');
taa[i] = taa[i-1] + (c1=='t' && c2=='a');
cta[i] = cta[i-1] + (c1=='c' && c2=='t');
tca[i] = tca[i-1] + (c1=='t' && c2=='c');
}
}
void init (string s1, string s2)
{
ll i;
n=s1.sz();
f0r(i,0,n-1)
{
a[i+1]=s1[i];
b[i+1]=s2[i];
}
build_pcas();
}
int get_distance (int x, int y)
{
y++;
if ((cntaa[y]-cntaa[x] != cntab[y]-cntab[x]) || (cntca[y]-cntca[x] != cntcb[y]-cntcb[x])) return -1;
ll ac=aca[y]-aca[x];
ll at=ata[y]-ata[x];
ll ca=caa[y]-caa[x];
ll ta=taa[y]-taa[x];
ll ct=cta[y]-cta[x];
ll tc=tca[y]-tca[x];
/*
printf("ac: %lli\n", ac);
printf("ca: %lli\n", ca);
printf("at: %lli\n", at);
printf("ta: %lli\n", ta);
printf("ct: %lli\n", ct);
printf("tc: %lli\n", tc);
*/
ll s = min(ac, ca) + min(at, ta) + min(ct, tc);
ac = abs(ac-ca);
ct = abs(ct-tc);
ta = abs(ta-at);
/*
printf("ac: %lli\n", ac);
printf("ct: %lli\n", ct);
printf("ta: %lli\n", ta);
*/
s+=2*ac;
return s;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
13400 KB |
Output is correct |
2 |
Correct |
37 ms |
13148 KB |
Output is correct |
3 |
Correct |
35 ms |
13096 KB |
Output is correct |
4 |
Correct |
36 ms |
13136 KB |
Output is correct |
5 |
Correct |
4 ms |
9820 KB |
Output is correct |
6 |
Correct |
4 ms |
9820 KB |
Output is correct |
7 |
Correct |
5 ms |
9816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
10072 KB |
Output is correct |
2 |
Correct |
4 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10076 KB |
Output is correct |
4 |
Correct |
13 ms |
10844 KB |
Output is correct |
5 |
Correct |
13 ms |
10832 KB |
Output is correct |
6 |
Correct |
13 ms |
11100 KB |
Output is correct |
7 |
Correct |
12 ms |
10804 KB |
Output is correct |
8 |
Correct |
13 ms |
10696 KB |
Output is correct |
9 |
Correct |
13 ms |
10844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
10072 KB |
Output is correct |
2 |
Correct |
4 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10076 KB |
Output is correct |
4 |
Correct |
13 ms |
10844 KB |
Output is correct |
5 |
Correct |
13 ms |
10832 KB |
Output is correct |
6 |
Correct |
13 ms |
11100 KB |
Output is correct |
7 |
Correct |
12 ms |
10804 KB |
Output is correct |
8 |
Correct |
13 ms |
10696 KB |
Output is correct |
9 |
Correct |
13 ms |
10844 KB |
Output is correct |
10 |
Correct |
36 ms |
13144 KB |
Output is correct |
11 |
Correct |
37 ms |
13132 KB |
Output is correct |
12 |
Correct |
37 ms |
13336 KB |
Output is correct |
13 |
Correct |
39 ms |
13592 KB |
Output is correct |
14 |
Correct |
40 ms |
13452 KB |
Output is correct |
15 |
Correct |
36 ms |
13564 KB |
Output is correct |
16 |
Correct |
36 ms |
13348 KB |
Output is correct |
17 |
Correct |
36 ms |
13344 KB |
Output is correct |
18 |
Correct |
37 ms |
13328 KB |
Output is correct |
19 |
Correct |
35 ms |
13340 KB |
Output is correct |
20 |
Correct |
36 ms |
13336 KB |
Output is correct |
21 |
Correct |
35 ms |
13592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
10072 KB |
Output is correct |
2 |
Correct |
4 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10076 KB |
Output is correct |
4 |
Correct |
13 ms |
10844 KB |
Output is correct |
5 |
Correct |
13 ms |
10832 KB |
Output is correct |
6 |
Correct |
13 ms |
11100 KB |
Output is correct |
7 |
Correct |
12 ms |
10804 KB |
Output is correct |
8 |
Correct |
13 ms |
10696 KB |
Output is correct |
9 |
Correct |
13 ms |
10844 KB |
Output is correct |
10 |
Correct |
12 ms |
10584 KB |
Output is correct |
11 |
Correct |
12 ms |
10844 KB |
Output is correct |
12 |
Correct |
12 ms |
10588 KB |
Output is correct |
13 |
Correct |
13 ms |
10844 KB |
Output is correct |
14 |
Correct |
13 ms |
10864 KB |
Output is correct |
15 |
Correct |
12 ms |
10844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
13400 KB |
Output is correct |
2 |
Correct |
37 ms |
13148 KB |
Output is correct |
3 |
Correct |
35 ms |
13096 KB |
Output is correct |
4 |
Correct |
36 ms |
13136 KB |
Output is correct |
5 |
Correct |
4 ms |
9820 KB |
Output is correct |
6 |
Correct |
4 ms |
9820 KB |
Output is correct |
7 |
Correct |
5 ms |
9816 KB |
Output is correct |
8 |
Correct |
4 ms |
10072 KB |
Output is correct |
9 |
Correct |
4 ms |
10076 KB |
Output is correct |
10 |
Correct |
4 ms |
10076 KB |
Output is correct |
11 |
Correct |
13 ms |
10844 KB |
Output is correct |
12 |
Correct |
13 ms |
10832 KB |
Output is correct |
13 |
Correct |
13 ms |
11100 KB |
Output is correct |
14 |
Correct |
12 ms |
10804 KB |
Output is correct |
15 |
Correct |
13 ms |
10696 KB |
Output is correct |
16 |
Correct |
13 ms |
10844 KB |
Output is correct |
17 |
Correct |
36 ms |
13144 KB |
Output is correct |
18 |
Correct |
37 ms |
13132 KB |
Output is correct |
19 |
Correct |
37 ms |
13336 KB |
Output is correct |
20 |
Correct |
39 ms |
13592 KB |
Output is correct |
21 |
Correct |
40 ms |
13452 KB |
Output is correct |
22 |
Correct |
36 ms |
13564 KB |
Output is correct |
23 |
Correct |
36 ms |
13348 KB |
Output is correct |
24 |
Correct |
36 ms |
13344 KB |
Output is correct |
25 |
Correct |
37 ms |
13328 KB |
Output is correct |
26 |
Correct |
35 ms |
13340 KB |
Output is correct |
27 |
Correct |
36 ms |
13336 KB |
Output is correct |
28 |
Correct |
35 ms |
13592 KB |
Output is correct |
29 |
Correct |
12 ms |
10584 KB |
Output is correct |
30 |
Correct |
12 ms |
10844 KB |
Output is correct |
31 |
Correct |
12 ms |
10588 KB |
Output is correct |
32 |
Correct |
13 ms |
10844 KB |
Output is correct |
33 |
Correct |
13 ms |
10864 KB |
Output is correct |
34 |
Correct |
12 ms |
10844 KB |
Output is correct |
35 |
Correct |
4 ms |
10076 KB |
Output is correct |
36 |
Correct |
34 ms |
13168 KB |
Output is correct |
37 |
Correct |
36 ms |
13148 KB |
Output is correct |
38 |
Correct |
38 ms |
13572 KB |
Output is correct |
39 |
Correct |
38 ms |
13584 KB |
Output is correct |
40 |
Correct |
37 ms |
13584 KB |
Output is correct |
41 |
Correct |
12 ms |
10840 KB |
Output is correct |
42 |
Correct |
36 ms |
13480 KB |
Output is correct |
43 |
Correct |
37 ms |
13324 KB |
Output is correct |
44 |
Correct |
40 ms |
13524 KB |
Output is correct |
45 |
Correct |
35 ms |
13336 KB |
Output is correct |
46 |
Correct |
36 ms |
13324 KB |
Output is correct |
47 |
Correct |
35 ms |
13576 KB |
Output is correct |