結果
問題 | No.2018 X-Y-X |
ユーザー | ir5 |
提出日時 | 2024-06-15 23:58:17 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 3,387 bytes |
コンパイル時間 | 2,214 ms |
コンパイル使用メモリ | 151,412 KB |
実行使用メモリ | 5,504 KB |
最終ジャッジ日時 | 2024-06-15 23:58:22 |
合計ジャッジ時間 | 4,599 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 11 ms
5,504 KB |
testcase_07 | AC | 11 ms
5,504 KB |
testcase_08 | AC | 10 ms
5,376 KB |
testcase_09 | AC | 11 ms
5,504 KB |
testcase_10 | AC | 7 ms
5,376 KB |
testcase_11 | AC | 8 ms
5,376 KB |
testcase_12 | AC | 9 ms
5,376 KB |
testcase_13 | AC | 11 ms
5,376 KB |
testcase_14 | AC | 11 ms
5,376 KB |
testcase_15 | AC | 13 ms
5,376 KB |
testcase_16 | AC | 9 ms
5,376 KB |
testcase_17 | AC | 11 ms
5,376 KB |
testcase_18 | AC | 7 ms
5,376 KB |
testcase_19 | AC | 10 ms
5,376 KB |
testcase_20 | AC | 13 ms
5,376 KB |
testcase_21 | AC | 10 ms
5,376 KB |
testcase_22 | AC | 11 ms
5,376 KB |
testcase_23 | AC | 3 ms
5,376 KB |
testcase_24 | AC | 12 ms
5,376 KB |
testcase_25 | AC | 13 ms
5,376 KB |
testcase_26 | AC | 10 ms
5,376 KB |
testcase_27 | AC | 6 ms
5,376 KB |
testcase_28 | AC | 3 ms
5,376 KB |
testcase_29 | AC | 4 ms
5,376 KB |
testcase_30 | AC | 6 ms
5,376 KB |
testcase_31 | AC | 8 ms
5,376 KB |
testcase_32 | AC | 10 ms
5,376 KB |
ソースコード
#include <algorithm> #include <cassert> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <tuple> #include <vector> #include <map> #include <set> #include <queue> #include <ranges> #include <iomanip> #include <bitset> using namespace std; using ll = long long; auto range(int n) { return views::iota(0, n); } #define repeat(n) for ([[maybe_unused]] auto : range(n)) template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; } template<typename T> ostream& operator<<(ostream& os, const vector<T>& obj) { os << "{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template<typename T> ostream& operator<<(ostream& os, const set<T>& obj) { os << "set{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template<typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& obj) { os << "map{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } #ifdef ONLINE_JUDGE #define dump(expr) ; #else #define dump(expr) { cerr << "\033[33m#L" << __LINE__ << ": " << expr << "\033[39m" << endl; } #endif struct UFWithWeights { vector<int> data, weights; UFWithWeights(int n) : data(n, -1), weights(n, 1) {} int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } bool find(int x, int y) { return root(x) == root(y); } void uni(int x, int y) { x = root(x); y = root(y); if (x != y) { int new_weight = weights[x] + weights[y]; if (data[x] < data[y]) swap(x, y); data[x] += data[y]; data[y] = x; weights[x] = new_weight; } } int weight(int x) { return weights[root(x)]; } }; int get(int x, int i) { return (x >> i) & 1; } void experiment() { const int n = 11; UFWithWeights uf(1 << n); for (int x : range(1 << n)) { for (int i : range(n - 2)) { if (get(x, i) == get(x, i + 2)) { int y = x ^ (1 << (i + 1)); uf.uni(x, y); } } } vector<vector<int>> vss(1 << n); for (int x : range(1 << n)) vss[uf.root(x)].push_back(x); for (auto vs : vss) if (vs.size() > 0) { int m = *min(vs.begin(), vs.end()); // cout << vs << endl; auto s = bitset<n>(m).to_string(); if (s[0] == '0' && s[n - 1] == '0') { for (auto x : vs) cout << bitset<n>(x).to_string() << " "; cout << endl; } } } ll solve() { int n; cin >> n; string s_in, t_in; cin >> s_in >> t_in; if (s_in[0] != t_in[0]) return -1; if (s_in[n - 1] != t_in[n - 1]) return -1; vector<int> s(n - 1), t(n - 1); for (int i : range(n - 1)) { s[i] = (s_in[i] - 'A') ^ (s_in[i + 1] - 'A'); t[i] = (t_in[i] - 'A') ^ (t_in[i + 1] - 'A'); } dump(s); dump(t); int i = 0, j = 0; ll res = 0; while (i < n - 1 && j < n - 1) { // In [0, i), s and t are the same // In [i, j), s and t are not the same and s is alternating if (s[i] == t[i]) { i++; continue; } assert(s[i] != t[i]); if (j < i) j = i; if (j - 1 >= i && s[j] == s[j - 1]) { // i j // 01010100 // -> // 11010101 res += j - i; s[i] ^= 1; s[j] ^= 1; } else { j++; } } if (i == n - 1) return res; else return -1; } int main() { cout << fixed << setprecision(12); // experiment(); cout << solve() << endl; }