結果
問題 | No.1209 XOR Into You |
ユーザー |
![]() |
提出日時 | 2020-08-30 14:12:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 2,008 bytes |
コンパイル時間 | 2,514 ms |
コンパイル使用メモリ | 209,832 KB |
最終ジャッジ日時 | 2025-01-13 21:41:29 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:69:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 69 | for(int i=0;i<N;i++)scanf("%d",&A[i]); | ~~~~~^~~~~~~~~~~~ main.cpp:70:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 70 | for(int i=0;i<N;i++)scanf("%d",&B[i]); | ~~~~~^~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 2000000000000000000 template <typename T> struct BIT{ vector<T> v; int n; T init_value = 0; BIT(int sz=0){ n=sz+1; v.resize(n,init_value); } BIT(vector<T> &x){ n=x.size()+1; v.resize(n,init_value); for(int i=0;i<x.size();i++){ add(i,x[i]); } } void add(int x,T val){ x++; while(x < n){ v[x] = func(v[x],val); x += x & (-x); } } //区間[0,r)におけるクエリ処理 T query(int r){ T ret = init_value; while(r>0){ ret = func(v[r],ret); r -= r & (-r); } return ret; } T query(int l,int r){ return query(r) - query(l); } T func(T a,T b){ return a+b; } int size(){ return n-1; } }; int main(){ int N; cin>>N; vector<int> A(N),B(N); for(int i=0;i<N;i++)scanf("%d",&A[i]); for(int i=0;i<N;i++)scanf("%d",&B[i]); if(A[0]!=B[0]||A.back()!=B.back()){ cout<<-1<<endl; return 0; } vector<int> C(N-1),D(N-1); for(int i=0;i<N-1;i++){ C[i] = A[i]^A[i+1]; D[i] = B[i]^B[i+1]; } { auto x = C,y = D; sort(x.begin(),x.end()); sort(y.begin(),y.end()); if(x!=y){ cout<<-1<<endl; return 0; } { map<int,int> cnt; for(int i=0;i<C.size();i++){ int d = distance(x.begin(),lower_bound(x.begin(),x.end(),C[i])); cnt[C[i]]++; C[i] = d+cnt[C[i]]-1; } } { map<int,int> cnt; for(int i=0;i<D.size();i++){ int d = distance(x.begin(),lower_bound(x.begin(),x.end(),D[i])); cnt[D[i]]++; D[i] = d+cnt[D[i]]-1; } } } vector<int> E(N-1); for(int i=0;i<N-1;i++){ E[C[i]] = i; } for(int i=0;i<N-1;i++){ D[i] = E[D[i]]; } swap(E,D); vector<int> pos(N-1); for(int i=0;i<N-1;i++){ pos[E[i]]=i; } BIT<long long> Bi(E.size()); long long ans = 0LL; for(int i=0;i<N-1;i++){ ans += Bi.query(pos[i],Bi.size()); Bi.add(pos[i],1LL); } cout<<ans<<endl; return 0; }