#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define pry cout << "YES\n"
#define prn cout << "NO\n"
#define endl '\n'
#define fst first
#define scn second
/* #define ONPC */
struct sump {
int n;
vector<int> a;
vector<int> tr;
sump() {}
void
set(int _n) {
n = _n;
a.assign(n,0);
tr.assign(n,0);
}
void
add(int x)
{
++a[x];
return;
}
void
gen()
{
for (int i = 0; i < n; ++i) {
if (i) tr[i] = tr[i-1];
tr[i] += a[i];
}
return;
}
int
query(int x)
{
if (x < 0)
return 0;
return tr[x];
}
int
query(int l, int r)
{
return query(r) - query(l-1);
}
};
sump aa, at, ac;
sump ba, bt, bc;
sump t[6];
void
init(string a, string b)
{
int n = sz(a);
aa.set(n);
at.set(n);
ac.set(n);
ba.set(n);
bt.set(n);
bc.set(n);
for (int i = 0; i < 6; ++i) t[i].set(n);
for (int i = 0; i < n; ++i) {
if (a[i] == 'A') {
aa.add(i);
if (b[i] == 'C') t[0].add(i);
if (b[i] == 'T') t[1].add(i);
}
if (a[i] == 'C') {
ac.add(i);
if (b[i] == 'A') t[2].add(i);
if (b[i] == 'T') t[3].add(i);
}
if (a[i] == 'T') {
at.add(i);
if (b[i] == 'A') t[4].add(i);
if (b[i] == 'C') t[5].add(i);
}
if (b[i] == 'A') ba.add(i);
if (b[i] == 'C') bc.add(i);
if (b[i] == 'T') bt.add(i);
}
aa.gen();
at.gen();
ac.gen();
ba.gen();
bt.gen();
bc.gen();
for (int i = 0; i < 6; ++i) t[i].gen();
return;
}
int
get_distance(int x, int y)
{
int v[6];
if (aa.query(x,y) != ba.query(x,y)) return -1;
if (ac.query(x,y) != bc.query(x,y)) return -1;
assert(at.query(x,y) == bt.query(x,y));
if (at.query(x,y) != bt.query(x,y)) return -1; /* USELESS */
for (int i = 0; i < 6; ++i) {
v[i] = t[i].query(x,y);
}
int ans = 0;
int a, b, c;
a = min(v[0], v[2]);
b = min(v[1], v[4]);
c = min(v[3], v[5]);
v[0] -= a;
v[2] -= a;
v[1] -= b;
v[4] -= b;
v[3] -= c;
v[5] -= c;
ans = a + b + c;
ans += (v[0]<<1);
ans += (v[1]<<1);
return ans;
}
#ifdef ONPC
void
solve()
{
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
11388 KB |
Output is correct |
2 |
Correct |
40 ms |
12944 KB |
Output is correct |
3 |
Correct |
40 ms |
12036 KB |
Output is correct |
4 |
Correct |
52 ms |
12872 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
8 ms |
10356 KB |
Output is correct |
5 |
Correct |
8 ms |
10424 KB |
Output is correct |
6 |
Correct |
8 ms |
10416 KB |
Output is correct |
7 |
Correct |
7 ms |
9684 KB |
Output is correct |
8 |
Correct |
8 ms |
10452 KB |
Output is correct |
9 |
Correct |
8 ms |
10452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
8 ms |
10356 KB |
Output is correct |
5 |
Correct |
8 ms |
10424 KB |
Output is correct |
6 |
Correct |
8 ms |
10416 KB |
Output is correct |
7 |
Correct |
7 ms |
9684 KB |
Output is correct |
8 |
Correct |
8 ms |
10452 KB |
Output is correct |
9 |
Correct |
8 ms |
10452 KB |
Output is correct |
10 |
Correct |
41 ms |
12812 KB |
Output is correct |
11 |
Correct |
40 ms |
12912 KB |
Output is correct |
12 |
Correct |
44 ms |
12536 KB |
Output is correct |
13 |
Correct |
50 ms |
12852 KB |
Output is correct |
14 |
Correct |
39 ms |
13272 KB |
Output is correct |
15 |
Correct |
41 ms |
13236 KB |
Output is correct |
16 |
Correct |
42 ms |
12412 KB |
Output is correct |
17 |
Correct |
42 ms |
12792 KB |
Output is correct |
18 |
Correct |
37 ms |
13192 KB |
Output is correct |
19 |
Correct |
36 ms |
12504 KB |
Output is correct |
20 |
Correct |
36 ms |
12780 KB |
Output is correct |
21 |
Correct |
35 ms |
13132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
8 ms |
10356 KB |
Output is correct |
5 |
Correct |
8 ms |
10424 KB |
Output is correct |
6 |
Correct |
8 ms |
10416 KB |
Output is correct |
7 |
Correct |
7 ms |
9684 KB |
Output is correct |
8 |
Correct |
8 ms |
10452 KB |
Output is correct |
9 |
Correct |
8 ms |
10452 KB |
Output is correct |
10 |
Correct |
8 ms |
9612 KB |
Output is correct |
11 |
Correct |
9 ms |
10420 KB |
Output is correct |
12 |
Correct |
8 ms |
9796 KB |
Output is correct |
13 |
Correct |
9 ms |
10412 KB |
Output is correct |
14 |
Correct |
9 ms |
10504 KB |
Output is correct |
15 |
Correct |
8 ms |
10452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
11388 KB |
Output is correct |
2 |
Correct |
40 ms |
12944 KB |
Output is correct |
3 |
Correct |
40 ms |
12036 KB |
Output is correct |
4 |
Correct |
52 ms |
12872 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
8 ms |
10356 KB |
Output is correct |
12 |
Correct |
8 ms |
10424 KB |
Output is correct |
13 |
Correct |
8 ms |
10416 KB |
Output is correct |
14 |
Correct |
7 ms |
9684 KB |
Output is correct |
15 |
Correct |
8 ms |
10452 KB |
Output is correct |
16 |
Correct |
8 ms |
10452 KB |
Output is correct |
17 |
Correct |
41 ms |
12812 KB |
Output is correct |
18 |
Correct |
40 ms |
12912 KB |
Output is correct |
19 |
Correct |
44 ms |
12536 KB |
Output is correct |
20 |
Correct |
50 ms |
12852 KB |
Output is correct |
21 |
Correct |
39 ms |
13272 KB |
Output is correct |
22 |
Correct |
41 ms |
13236 KB |
Output is correct |
23 |
Correct |
42 ms |
12412 KB |
Output is correct |
24 |
Correct |
42 ms |
12792 KB |
Output is correct |
25 |
Correct |
37 ms |
13192 KB |
Output is correct |
26 |
Correct |
36 ms |
12504 KB |
Output is correct |
27 |
Correct |
36 ms |
12780 KB |
Output is correct |
28 |
Correct |
35 ms |
13132 KB |
Output is correct |
29 |
Correct |
8 ms |
9612 KB |
Output is correct |
30 |
Correct |
9 ms |
10420 KB |
Output is correct |
31 |
Correct |
8 ms |
9796 KB |
Output is correct |
32 |
Correct |
9 ms |
10412 KB |
Output is correct |
33 |
Correct |
9 ms |
10504 KB |
Output is correct |
34 |
Correct |
8 ms |
10452 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
38 ms |
12072 KB |
Output is correct |
37 |
Correct |
55 ms |
12944 KB |
Output is correct |
38 |
Correct |
50 ms |
12692 KB |
Output is correct |
39 |
Correct |
40 ms |
13284 KB |
Output is correct |
40 |
Correct |
51 ms |
13264 KB |
Output is correct |
41 |
Correct |
8 ms |
10452 KB |
Output is correct |
42 |
Correct |
50 ms |
12632 KB |
Output is correct |
43 |
Correct |
38 ms |
13172 KB |
Output is correct |
44 |
Correct |
38 ms |
13176 KB |
Output is correct |
45 |
Correct |
36 ms |
12692 KB |
Output is correct |
46 |
Correct |
35 ms |
13184 KB |
Output is correct |
47 |
Correct |
47 ms |
13176 KB |
Output is correct |