結果
問題 | No.1209 XOR Into You |
ユーザー |
|
提出日時 | 2020-11-17 22:03:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 1,317 bytes |
コンパイル時間 | 864 ms |
コンパイル使用メモリ | 78,784 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 08:30:45 |
合計ジャッジ時間 | 5,869 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
コンパイルメッセージ
a.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
ソースコード
#line 1 "a.cpp"#include<iostream>#include<algorithm>#include<vector>using namespace std;#line 1 "/home/kotatsugame/library/datastructure/BIT.cpp"//1-indexed#line 3 "/home/kotatsugame/library/datastructure/BIT.cpp"template<typename T>struct BIT{int n;vector<T>bit;BIT(int n_=0):n(n_),bit(n_+1){}T sum(int i){T ans=0;for(;i>0;i-=i&-i)ans+=bit[i];return ans;}void add(int i,T a){if(i==0)return;for(;i<=n;i+=i&-i)bit[i]+=a;}int lower_bound(T k)//k<=sum(ret){if(k<=0)return 0;int ret=0,i=1;while((i<<1)<=n)i<<=1;for(;i;i>>=1)if(ret+i<=n&&bit[ret+i]<k)k-=bit[ret+=i];return ret+1;}};#line 6 "a.cpp"int N;int A[1<<17],B[1<<17];int id[1<<17];main(){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]||A[N-1]!=B[N-1]){cout<<-1<<endl;return 0;}long ans=0;BIT<int>P(N-1);vector<pair<int,int> >a(N-1),b(N-1);for(int i=0;i<N-1;i++){a[i]=make_pair(A[i]^A[i+1],i);b[i]=make_pair(B[i]^B[i+1],i);}sort(a.begin(),a.end());sort(b.begin(),b.end());for(int i=0;i<N-1;i++){if(a[i].first!=b[i].first){cout<<-1<<endl;return 0;}id[a[i].second]=b[i].second;}for(int i=0;i<N-1;i++){int j=id[i]+(i-P.sum(id[i]));P.add(id[i]+1,1);ans+=j-i;}cout<<ans<<endl;}