結果
問題 | No.1209 XOR Into You |
ユーザー |
![]() |
提出日時 | 2020-07-29 01:57:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 273 ms / 2,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 1,638 ms |
コンパイル使用メモリ | 185,352 KB |
実行使用メモリ | 80,716 KB |
最終ジャッジ日時 | 2024-06-28 21:09:30 |
合計ジャッジ時間 | 11,969 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define int long long #define rep(i,n) for(int i=0;i<n;i++) #define vi vector<int> #define all(a) a.begin(),a.end() typedef pair<int,int> P; const long long mod=998244353; const long long inf=1ll<<61; int BIT[100006]; int a[100006],b[100006]; void add(int i,int x){ while(i<=100002){ BIT[i]+=x; i+=i&-i; } } int sum(int i){ int s=0; while(i>0){ s+=BIT[i]; i-=i&-i; } return s; } bool eq(vi a,vi b){ sort(all(a)); sort(all(b)); return a==b; } deque<int>Q[100006]; signed main(){ int n;cin>>n; rep(i,n)cin>>a[i]; rep(i,n)cin>>b[i]; if(a[0]!=b[0]||a[n-1]!=b[n-1]){ cout<<-1<<endl; return 0; } vector<int>na,nb; rep(i,n-1){ na.push_back(a[i]^a[i+1]); nb.push_back(b[i]^b[i+1]); } if(!eq(na,nb)){ cout<<-1<<endl; return 0; } map<int,int>M; n--; rep(i,n)M[na[i]]++; int cn=0; for(auto itr=M.begin();itr!=M.end();itr++){ M[itr->first]=cn;cn++; } rep(i,n){ na[i]=M[na[i]];nb[i]=M[nb[i]]; } rep(i,n){ Q[na[i]].push_back(i); add(i+1,1); } int ans=0; rep(i,n){ int k=Q[nb[i]].front();Q[nb[i]].pop_front(); ans+=sum(k); add(k+1,-1); } cout<<ans<<endl; }