#include "dna.h"
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
int n;
vector<int> cnta[3], cntb[3], p[3], rp[3];
char c[] = {'A', 'C', 'T'};
int to_int(char cc) {
rep(i, 0, 2) if(cc == c[i])
return i;
return -1;
}
void init(string a, string b) {
n = a.size();
rep(i, 0, 2) {
cnta[i].assign(n + 1, 0);
cntb[i].assign(n + 1, 0);
p[i].assign(n + 1, 0);
rp[i].assign(n + 1, 0);
}
rep(i, 1, n) {
int ca = to_int(a[i - 1]), cb = to_int(b[i - 1]);
cnta[ca][i] ++, cntb[cb][i] ++;
if(ca == cb);
else if(ca > cb) p[ca + cb - 1][i] ++;
else rp[ca + cb - 1][i] ++;
rep(j, 0, 2) {
cnta[j][i] += cnta[j][i - 1];
cntb[j][i] += cntb[j][i - 1];
p[j][i] += p[j][i - 1];
rp[j][i] += rp[j][i - 1];
}
}
return;
}
int get_distance(int x, int y) {
x++, y++;
rep(i, 0, 2) if(cnta[i][y] - cnta[i][x - 1]
!= cntb[i][y] - cntb[i][x - 1]) {
return -1;
}
int ans = 0, odd;
rep(i, 0, 2) {
int pos = p[i][y] - p[i][x - 1];
int neg = rp[i][y] - rp[i][x - 1];
odd = abs(pos - neg);
ans += min(pos, neg);
}
ans += odd * 2;
return ans;
}
Compilation message
dna.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
5 | #pragma loop-opt(on)
|
dna.cpp:25:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
25 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
dna.cpp:25:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
25 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
6788 KB |
Output is correct |
2 |
Correct |
56 ms |
6784 KB |
Output is correct |
3 |
Correct |
54 ms |
6380 KB |
Output is correct |
4 |
Correct |
62 ms |
6900 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
19 ms |
5552 KB |
Output is correct |
5 |
Correct |
20 ms |
5580 KB |
Output is correct |
6 |
Correct |
20 ms |
5544 KB |
Output is correct |
7 |
Correct |
18 ms |
5232 KB |
Output is correct |
8 |
Correct |
20 ms |
5580 KB |
Output is correct |
9 |
Correct |
19 ms |
5612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
19 ms |
5552 KB |
Output is correct |
5 |
Correct |
20 ms |
5580 KB |
Output is correct |
6 |
Correct |
20 ms |
5544 KB |
Output is correct |
7 |
Correct |
18 ms |
5232 KB |
Output is correct |
8 |
Correct |
20 ms |
5580 KB |
Output is correct |
9 |
Correct |
19 ms |
5612 KB |
Output is correct |
10 |
Correct |
58 ms |
6784 KB |
Output is correct |
11 |
Correct |
56 ms |
6784 KB |
Output is correct |
12 |
Correct |
56 ms |
6828 KB |
Output is correct |
13 |
Correct |
58 ms |
6940 KB |
Output is correct |
14 |
Correct |
58 ms |
7164 KB |
Output is correct |
15 |
Correct |
59 ms |
7084 KB |
Output is correct |
16 |
Correct |
55 ms |
6832 KB |
Output is correct |
17 |
Correct |
56 ms |
7040 KB |
Output is correct |
18 |
Correct |
54 ms |
7196 KB |
Output is correct |
19 |
Correct |
50 ms |
6800 KB |
Output is correct |
20 |
Correct |
53 ms |
7036 KB |
Output is correct |
21 |
Correct |
53 ms |
7192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
19 ms |
5552 KB |
Output is correct |
5 |
Correct |
20 ms |
5580 KB |
Output is correct |
6 |
Correct |
20 ms |
5544 KB |
Output is correct |
7 |
Correct |
18 ms |
5232 KB |
Output is correct |
8 |
Correct |
20 ms |
5580 KB |
Output is correct |
9 |
Correct |
19 ms |
5612 KB |
Output is correct |
10 |
Correct |
18 ms |
5172 KB |
Output is correct |
11 |
Correct |
20 ms |
5612 KB |
Output is correct |
12 |
Correct |
19 ms |
5196 KB |
Output is correct |
13 |
Correct |
20 ms |
5596 KB |
Output is correct |
14 |
Correct |
20 ms |
5580 KB |
Output is correct |
15 |
Correct |
19 ms |
5612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
6788 KB |
Output is correct |
2 |
Correct |
56 ms |
6784 KB |
Output is correct |
3 |
Correct |
54 ms |
6380 KB |
Output is correct |
4 |
Correct |
62 ms |
6900 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
19 ms |
5552 KB |
Output is correct |
12 |
Correct |
20 ms |
5580 KB |
Output is correct |
13 |
Correct |
20 ms |
5544 KB |
Output is correct |
14 |
Correct |
18 ms |
5232 KB |
Output is correct |
15 |
Correct |
20 ms |
5580 KB |
Output is correct |
16 |
Correct |
19 ms |
5612 KB |
Output is correct |
17 |
Correct |
58 ms |
6784 KB |
Output is correct |
18 |
Correct |
56 ms |
6784 KB |
Output is correct |
19 |
Correct |
56 ms |
6828 KB |
Output is correct |
20 |
Correct |
58 ms |
6940 KB |
Output is correct |
21 |
Correct |
58 ms |
7164 KB |
Output is correct |
22 |
Correct |
59 ms |
7084 KB |
Output is correct |
23 |
Correct |
55 ms |
6832 KB |
Output is correct |
24 |
Correct |
56 ms |
7040 KB |
Output is correct |
25 |
Correct |
54 ms |
7196 KB |
Output is correct |
26 |
Correct |
50 ms |
6800 KB |
Output is correct |
27 |
Correct |
53 ms |
7036 KB |
Output is correct |
28 |
Correct |
53 ms |
7192 KB |
Output is correct |
29 |
Correct |
18 ms |
5172 KB |
Output is correct |
30 |
Correct |
20 ms |
5612 KB |
Output is correct |
31 |
Correct |
19 ms |
5196 KB |
Output is correct |
32 |
Correct |
20 ms |
5596 KB |
Output is correct |
33 |
Correct |
20 ms |
5580 KB |
Output is correct |
34 |
Correct |
19 ms |
5612 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
56 ms |
6420 KB |
Output is correct |
37 |
Correct |
56 ms |
6900 KB |
Output is correct |
38 |
Correct |
57 ms |
6924 KB |
Output is correct |
39 |
Correct |
57 ms |
7204 KB |
Output is correct |
40 |
Correct |
57 ms |
7208 KB |
Output is correct |
41 |
Correct |
19 ms |
5524 KB |
Output is correct |
42 |
Correct |
54 ms |
6900 KB |
Output is correct |
43 |
Correct |
57 ms |
7168 KB |
Output is correct |
44 |
Correct |
55 ms |
7212 KB |
Output is correct |
45 |
Correct |
55 ms |
6904 KB |
Output is correct |
46 |
Correct |
53 ms |
7292 KB |
Output is correct |
47 |
Correct |
53 ms |
7288 KB |
Output is correct |