結果

問題 No.1209 XOR Into You
コンテスト
ユーザー vjudge1
提出日時 2026-11-10 20:12:20
言語 C++14
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 46 ms / 2,000 ms
+ 216µs
コード長 1,286 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,412 ms
コンパイル使用メモリ 188,820 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2026-11-10 20:12:31
合計ジャッジ時間 8,639 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge1_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, a[N], b[N], c[N], d[N], cnt[N], pos[N];
struct BIT {
	int t[N];
	void modify(int x, int v) {for (; x <= n; x += (x & -x)) t[x] += v;}
	int query(int x) {int ans = 0; for (; x; x -= (x & -x)) ans += t[x]; return ans;}
} T;
bool check() {
	sort(c + 1, c + n + 1), sort(d + 1, d + n + 1);
	for (int i = 1; i <= n; i++) if (c[i] != d[i]) return 0;
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(c + 1, c + n + 1, a[i]) - c;
		a[i] = x + cnt[x], cnt[x]++, pos[a[i]] = i;
	}
	for (int i = 1; i <= n; i++) cnt[i] = 0;
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(c + 1, c + n + 1, b[i]) - c;
		b[i] = x + cnt[x], cnt[x]++, b[i] = pos[b[i]];
	}
	return 1;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	if (a[1] != b[1]) cout << "-1\n", exit(0);
	for (int i = 1; i < n; i++) a[i] ^= a[i + 1], b[i] ^= b[i + 1], swap(a[i], b[i]);
	n--;
	for (int i = 1; i <= n; i++) c[i] = a[i], d[i] = b[i];
	if (!check()) cout << "-1\n", exit(0);
	ll ans = 0;
	for (int i = 1; i <= n; i++) ans += (i - 1) - T.query(b[i] - 1), T.modify(b[i], 1);
	cout << ans << '\n';
	return 0;
}
0