結果
問題 | No.1209 XOR Into You |
ユーザー |
|
提出日時 | 2023-01-28 02:04:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 1,501 bytes |
コンパイル時間 | 2,116 ms |
コンパイル使用メモリ | 208,908 KB |
最終ジャッジ日時 | 2025-02-10 07:27:06 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define fi first#define se second#define pb push_backusing vi = vector <int>;using ll = long long;using vl = vector <ll>;using pii = pair <int, int>;//~ const ll mod = 998244353;const ll mod = 1e9 + 7;ll qpow(ll a, ll b, ll m = mod) { ll r = 1, t = a;for(; b; b /= 2) { if(b & 1) r = r * t % m; t = t * t % m; } return r; }const int N = 2e5 + 11;int a[N], b[N];int p[N];struct event {int x, t;bool operator <(const event &e) const {return x < e.x;}};ll solve(int l, int r) {if(l + 1 == r) return 0;int m = (l + r) / 2;ll re = solve(l, m) + solve(m, r);vector <event> es;for(int i = l; i < m; i ++)es.pb({p[i], 0});for(int i = m; i < r; i ++)es.pb({p[i], 1});int cnt = 0;sort(es.begin(), es.end());for(auto e : es)if(e.t == 1) cnt ++;else re += cnt;return re;}int main() {ios :: sync_with_stdio(false);int n; cin >> n;for(int i = 0; i < n; i ++) cin >> a[i];for(int i = 0; i < n; i ++) cin >> b[i];if(a[0] != b[0]) {cout << "-1\n";return 0;}map <int, vi> ma, mb;for(int i = 0; i < n - 1; i ++) {ma[a[i] ^ a[i + 1]].pb(i);mb[b[i] ^ b[i + 1]].pb(i);}for(auto &[x, u] : ma) {auto &v = mb[x];if(u.size() != v.size()) {cout << "-1\n";return 0;}for(int i = 0; i < u.size(); i ++) {p[u[i]] = v[i];}}//~ for(int i = 0; i < n - 1; i ++)//~ cout << p[i] << ' ';//~ cout << '\n';cout << solve(0, n - 1) << '\n';}