結果
問題 | No.1296 OR or NOR |
ユーザー |
👑 ![]() |
提出日時 | 2020-11-20 22:26:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 737 ms / 3,000 ms |
コード長 | 1,409 bytes |
コンパイル時間 | 2,418 ms |
コンパイル使用メモリ | 199,540 KB |
最終ジャッジ日時 | 2025-01-16 02:38:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h>using namespace std;using LL=long long;using ULL=unsigned long long;#define rep(i,n) for(int i=0;i<(n);i++)int N,Q;vector<ULL> A;int main(){cin>>N;A.resize(N);rep(i,N) cin>>A[i];vector<ULL> G;ULL no;bool cannot_fix=false;{int dcrA[60];int rA[60]; rep(i,60) rA[i]=-1;rep(i,N) rep(d,60) if((A[i]>>d)&1) rA[d]=i;pair<int,int> S[61];S[0] = {-1,-1};rep(i,60){ S[i+1] = {rA[i],i}; }sort(S,S+61);int p=-1;rep(i,60){if(S[i+1].first!=S[i].first) p++;dcrA[S[i+1].second]=p;}G.resize(p+1);no=0;rep(i,60){if(dcrA[i]==-1) no |= 1ull<<i;else G[dcrA[i]] |= 1ull<<i;}rep(i,61) if(S[i].first==0) cannot_fix=true;}cin>>Q;while(Q--){ULL b; cin>>b;bool enable = true;int no_flipped=0;if((no&b) == 0){ no_flipped=0; }else if((no&b) == no){ no_flipped=1; }else enable=false;for(ULL g:G) if(((g&b) != g) && ((g&b) != 0)) enable=false;int flipped = 0;int ans=0;for(int i=G.size()-1; i>=0 && enable; i--){ULL g = G[i];int flip=1; if(g&b) flip=0;if(flipped != flip) ans++;flipped = flip;}if(no) if(ans%2 != no_flipped) {ans++;if(cannot_fix){ enable=false; }}if(!enable){ cout<<-1<<endl; continue; }cout<<ans<<endl;}return 0;}