#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class T, class U> istream& operator>>(istream &is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T> istream& operator>>(istream& is, vector<T>& vec) { for(auto &x : vec) cin >> x; return is; }
template<class T, class U> ostream& operator<<(ostream &os, pair<T, U>& p) { os << "<" << p.first << "," << p.second << ">"; return os; }
template<class T> ostream& operator<<(ostream& os, vector<T>& vec) { for(auto x : vec) os << x << " "; return os; }
int conv(char c) {
if (c == 'A') return 0;
else if (c == 'C') return 1;
return 2;
}
const int TYPES = 9, MAXN = 100010;
int prefs[TYPES][MAXN];
int n;
void init(string sa, string sb) {
n = sa.size();
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
a[i] = conv(sa[i]);
b[i] = conv(sb[i]);
}
for (int i = 0; i < n; i++) {
int type = a[i] * 3 + b[i];
prefs[type][i]++;
if (i > 0) {
for (int t = 0; t < TYPES; t++) {
prefs[t][i] += prefs[t][i-1];
}
}
}
}
int get_sum(int type, int l, int r) {
if (l == 0) return prefs[type][r];
return prefs[type][r] - prefs[type][l-1];
}
const vector<int> refl = {0,3,6,1,4,7,2,5,8};
pair<int, int> comb(int x, int y) {
pair<int, int> res;
int xi = x / 3, xj = x % 3;
int yi = y / 3, yj = y % 3;
res.first = xi * 3 + yj;
res.second = yi * 3 + xj;
return res;
}
int get_distance(int l, int r) {
vector<int> type_sums(TYPES);
for (int t = 0; t < TYPES; t++) {
type_sums[t] = get_sum(t, l, r);
}
int swaps = 0;
// cancel out on diagonal.
swaps += min(type_sums[1], type_sums[3]);
swaps += min(type_sums[2], type_sums[6]);
swaps += min(type_sums[5], type_sums[7]);
vector<int> rems = {
type_sums[1] - type_sums[3],
type_sums[2] - type_sums[6],
type_sums[5] - type_sums[7]
};
if (abs(rems[0]) == abs(rems[1]) && abs(rems[1]) == abs(rems[2])) {
if (rems[0] == 0) return swaps;
// if all the same sign, that's not good
int ct = 0;
for (int x = 0; x <= 2; x++) ct += rems[x] / abs(rems[x]);
if (abs(ct) == 3) return -1;
// is there a pair that we can combine
// such that it is a reflection of the third thing?
vector<int> elems;
if (rems[0] > 0) elems.push_back(1);
else elems.push_back(3);
if (rems[1] > 0) elems.push_back(2);
else elems.push_back(6);
if (rems[2] > 0) elems.push_back(5);
else elems.push_back(7);
for (int x = 0; x <= 2; x++) {
// x is the third thing
int target = refl[elems[x]];
int i = 0, j = 0;
while (i == x) i++;
while (j == i || j == x) j++;
pair<int, int> combination = comb(elems[i], elems[j]);
if (combination.first == target || combination.second == target) {
return swaps + abs(rems[0]) * 2;
}
}
return -1;
}
else return -1;
}
// int main() {
// int n, q; cin >> n >> q;
// string sa, sb; cin >> sa >> sb;
// init(sa, sb);
// for (int qq = 0; qq < q; qq++) {
// int l, r; cin >> l >> r;
// cout << get_distance(l, r) << '\n';
// }
// return 0;
// }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
6480 KB |
Output is correct |
2 |
Correct |
37 ms |
6492 KB |
Output is correct |
3 |
Correct |
38 ms |
6064 KB |
Output is correct |
4 |
Correct |
40 ms |
7628 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
5 ms |
5188 KB |
Output is correct |
5 |
Correct |
5 ms |
5268 KB |
Output is correct |
6 |
Correct |
5 ms |
5312 KB |
Output is correct |
7 |
Correct |
5 ms |
4972 KB |
Output is correct |
8 |
Correct |
5 ms |
5308 KB |
Output is correct |
9 |
Correct |
5 ms |
5252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
5 ms |
5188 KB |
Output is correct |
5 |
Correct |
5 ms |
5268 KB |
Output is correct |
6 |
Correct |
5 ms |
5312 KB |
Output is correct |
7 |
Correct |
5 ms |
4972 KB |
Output is correct |
8 |
Correct |
5 ms |
5308 KB |
Output is correct |
9 |
Correct |
5 ms |
5252 KB |
Output is correct |
10 |
Correct |
37 ms |
6472 KB |
Output is correct |
11 |
Correct |
38 ms |
6496 KB |
Output is correct |
12 |
Correct |
39 ms |
6072 KB |
Output is correct |
13 |
Correct |
39 ms |
6220 KB |
Output is correct |
14 |
Correct |
43 ms |
6600 KB |
Output is correct |
15 |
Correct |
37 ms |
6480 KB |
Output is correct |
16 |
Correct |
35 ms |
6064 KB |
Output is correct |
17 |
Correct |
38 ms |
6208 KB |
Output is correct |
18 |
Correct |
37 ms |
6496 KB |
Output is correct |
19 |
Correct |
36 ms |
6224 KB |
Output is correct |
20 |
Correct |
33 ms |
6324 KB |
Output is correct |
21 |
Correct |
36 ms |
6492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
5 ms |
5188 KB |
Output is correct |
5 |
Correct |
5 ms |
5268 KB |
Output is correct |
6 |
Correct |
5 ms |
5312 KB |
Output is correct |
7 |
Correct |
5 ms |
4972 KB |
Output is correct |
8 |
Correct |
5 ms |
5308 KB |
Output is correct |
9 |
Correct |
5 ms |
5252 KB |
Output is correct |
10 |
Correct |
5 ms |
4948 KB |
Output is correct |
11 |
Correct |
6 ms |
5308 KB |
Output is correct |
12 |
Correct |
5 ms |
5032 KB |
Output is correct |
13 |
Correct |
6 ms |
5332 KB |
Output is correct |
14 |
Correct |
5 ms |
5316 KB |
Output is correct |
15 |
Correct |
5 ms |
5316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
6480 KB |
Output is correct |
2 |
Correct |
37 ms |
6492 KB |
Output is correct |
3 |
Correct |
38 ms |
6064 KB |
Output is correct |
4 |
Correct |
40 ms |
7628 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 |
212 KB |
Output is correct |
11 |
Correct |
5 ms |
5188 KB |
Output is correct |
12 |
Correct |
5 ms |
5268 KB |
Output is correct |
13 |
Correct |
5 ms |
5312 KB |
Output is correct |
14 |
Correct |
5 ms |
4972 KB |
Output is correct |
15 |
Correct |
5 ms |
5308 KB |
Output is correct |
16 |
Correct |
5 ms |
5252 KB |
Output is correct |
17 |
Correct |
37 ms |
6472 KB |
Output is correct |
18 |
Correct |
38 ms |
6496 KB |
Output is correct |
19 |
Correct |
39 ms |
6072 KB |
Output is correct |
20 |
Correct |
39 ms |
6220 KB |
Output is correct |
21 |
Correct |
43 ms |
6600 KB |
Output is correct |
22 |
Correct |
37 ms |
6480 KB |
Output is correct |
23 |
Correct |
35 ms |
6064 KB |
Output is correct |
24 |
Correct |
38 ms |
6208 KB |
Output is correct |
25 |
Correct |
37 ms |
6496 KB |
Output is correct |
26 |
Correct |
36 ms |
6224 KB |
Output is correct |
27 |
Correct |
33 ms |
6324 KB |
Output is correct |
28 |
Correct |
36 ms |
6492 KB |
Output is correct |
29 |
Correct |
5 ms |
4948 KB |
Output is correct |
30 |
Correct |
6 ms |
5308 KB |
Output is correct |
31 |
Correct |
5 ms |
5032 KB |
Output is correct |
32 |
Correct |
6 ms |
5332 KB |
Output is correct |
33 |
Correct |
5 ms |
5316 KB |
Output is correct |
34 |
Correct |
5 ms |
5316 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
40 ms |
7188 KB |
Output is correct |
37 |
Correct |
42 ms |
7608 KB |
Output is correct |
38 |
Correct |
55 ms |
7372 KB |
Output is correct |
39 |
Correct |
53 ms |
7628 KB |
Output is correct |
40 |
Correct |
57 ms |
7620 KB |
Output is correct |
41 |
Correct |
5 ms |
5308 KB |
Output is correct |
42 |
Correct |
49 ms |
7244 KB |
Output is correct |
43 |
Correct |
47 ms |
7612 KB |
Output is correct |
44 |
Correct |
48 ms |
7512 KB |
Output is correct |
45 |
Correct |
46 ms |
7200 KB |
Output is correct |
46 |
Correct |
42 ms |
7484 KB |
Output is correct |
47 |
Correct |
43 ms |
7488 KB |
Output is correct |