結果
問題 | No.1209 XOR Into You |
ユーザー |
![]() |
提出日時 | 2020-08-30 14:52:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 1,588 bytes |
コンパイル時間 | 2,801 ms |
コンパイル使用メモリ | 212,212 KB |
最終ジャッジ日時 | 2025-01-13 22:04:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;long long inversion_number(vector<int> &p){int N = p.size();long long ans = 0;vector<int> bit(N + 1, 0);for (int i = 0; i < N; i++){ans += i;int j = p[i];while (j > 0){ans -= bit[j];j -= j & -j;}j = p[i];while (j <= N){bit[j]++;j += j & -j;}}return ans;}int main(){int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; i++){cin >> A[i];}vector<int> B(N);for (int i = 0; i < N; i++){cin >> B[i];}if (A[0] != B[0] || A[N - 1] != B[N - 1]){cout << -1 << endl;} else {vector<int> C(N - 1);for (int i = 0; i < N - 1; i++){C[i] = A[i] ^ A[i + 1];}vector<int> D(N - 1);for (int i = 0; i < N - 1; i++){D[i] = B[i] ^ B[i + 1];}vector<int> C2 = C;sort(C2.begin(), C2.end());vector<int> D2 = D;sort(D2.begin(), D2.end());if (C2 != D2){cout << -1 << endl;} else {map<int, int> mp;vector<pair<int, int>> E(N - 1);for (int i = 0; i < N - 1; i++){E[i] = make_pair(C[i], mp[C[i]]);mp[C[i]]++;}map<int, int> mp2;vector<pair<int, int>> F(N - 1);for (int i = 0; i < N - 1; i++){F[i] = make_pair(D[i], mp2[D[i]]);mp2[D[i]]++;}map<pair<int, int>, int> mp3;for (int i = 0; i < N - 1; i++){mp3[E[i]] = i;}vector<int> G(N - 1);for (int i = 0; i < N - 1; i++){G[i] = mp3[F[i]] + 1;}cout << inversion_number(G) << endl;}}}