結果
問題 | No.1296 OR or NOR |
ユーザー | LayCurse |
提出日時 | 2020-11-20 22:33:59 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,673 ms / 3,000 ms |
コード長 | 5,007 bytes |
コンパイル時間 | 2,749 ms |
コンパイル使用メモリ | 212,176 KB |
実行使用メモリ | 8,676 KB |
最終ジャッジ日時 | 2023-09-30 19:37:43 |
合計ジャッジ時間 | 23,931 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,392 KB |
testcase_01 | AC | 2 ms
5,360 KB |
testcase_02 | AC | 127 ms
8,456 KB |
testcase_03 | AC | 126 ms
8,640 KB |
testcase_04 | AC | 747 ms
8,408 KB |
testcase_05 | AC | 733 ms
8,640 KB |
testcase_06 | AC | 130 ms
8,420 KB |
testcase_07 | AC | 120 ms
8,612 KB |
testcase_08 | AC | 124 ms
8,412 KB |
testcase_09 | AC | 217 ms
8,444 KB |
testcase_10 | AC | 244 ms
8,488 KB |
testcase_11 | AC | 192 ms
8,676 KB |
testcase_12 | AC | 171 ms
8,404 KB |
testcase_13 | AC | 179 ms
8,408 KB |
testcase_14 | AC | 1,672 ms
8,504 KB |
testcase_15 | AC | 1,631 ms
8,500 KB |
testcase_16 | AC | 1,619 ms
8,504 KB |
testcase_17 | AC | 101 ms
8,452 KB |
testcase_18 | AC | 100 ms
8,584 KB |
testcase_19 | AC | 100 ms
8,636 KB |
testcase_20 | AC | 80 ms
7,944 KB |
testcase_21 | AC | 78 ms
7,960 KB |
testcase_22 | AC | 70 ms
7,944 KB |
testcase_23 | AC | 71 ms
8,024 KB |
testcase_24 | AC | 78 ms
7,976 KB |
testcase_25 | AC | 76 ms
7,944 KB |
testcase_26 | AC | 79 ms
7,960 KB |
testcase_27 | AC | 82 ms
8,012 KB |
testcase_28 | AC | 74 ms
7,980 KB |
testcase_29 | AC | 80 ms
8,104 KB |
testcase_30 | AC | 1,673 ms
8,608 KB |
testcase_31 | AC | 1,671 ms
8,496 KB |
testcase_32 | AC | 1,672 ms
8,496 KB |
testcase_33 | AC | 1,613 ms
8,424 KB |
testcase_34 | AC | 1,613 ms
8,412 KB |
ソースコード
#pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void rd(long long &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(long long x){ int s=0; int m=0; char f[20]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } template<class S, class T> inline S chmax(S &a, T b){ if(a<b){ a=b; } return a; } int N; int Q; long long A[200000]; long long B[200000]; int las[60]; int main(){ int hCmBdyQB, i, j; long long res; long long can; long long cur; long long now; long long nx; int ok0; int ok1; int str = 0; ; rd(N); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){ rd(A[Lj4PdHRW]); } } rd(Q); { int e98WHCEY; for(e98WHCEY=(0);e98WHCEY<(Q);e98WHCEY++){ rd(B[e98WHCEY]); } } for(j=(0);j<(60);j++){ las[j] = -1; } for(i=(0);i<(Q);i++){ for(j=(0);j<(60);j++){ if(A[i] & (1LL<<j)){ las[j] = i; } } } for(j=(0);j<(60);j++){ if(las[j]==0){ str = 1; } } for(hCmBdyQB=(0);hCmBdyQB<(Q);hCmBdyQB++){ auto &now = B[hCmBdyQB]; res = can = 0; cur = N; for(;;){ nx = -1; for(i=(0);i<(60);i++){ if(las[i] < cur){ chmax(nx, las[i]); } } if(nx == -1){ break; } ok0 = ok1 = 1; for(i=(0);i<(60);i++){ if(las[i] == nx){ if(now & (1LL << i)){ ok1 = 0; } if(!(now & (1LL << i))){ ok0 = 0; } } } if(ok0==ok1 && ok1==0){ wt_L(-1); wt_L('\n'); goto V9aVTaxx; } if(ok0==0){ res++; now ^= (1LL << 60) - 1; } cur = nx; } ok0 = ok1 = 1; for(i=(0);i<(60);i++){ if(las[i]==-1){ if(now & (1LL << i)){ ok0 = 0; } if(!(now & (1LL << i))){ ok1 = 0; } } } if(ok0==ok1 && ok1==0 || (str==1 && ok0==0)){ wt_L(-1); wt_L('\n'); continue; } if(ok0==0){ res++; } wt_L(res); wt_L('\n'); V9aVTaxx:; } return 0; } // cLay version 20201120-1 [beta] // --- original code --- // int N, Q; ll A[2d5], B[2d5]; // int las[60]; // // { // ll res, can, cur, now, nx; // int ok0, ok1, str = 0;; // rd(N,A(N),Q,B(Q)); // // rep(j,60) las[j] = -1; // rep(i,Q) rep(j,60) if(A[i] & (1LL<<j)) las[j] = i; // rep(j,60) if(las[j]==0) str = 1; // // rep[B](now,Q){ // res = can = 0; // cur = N; // // for(;;){ // nx = -1; // rep(i,60) if(las[i] < cur) nx >?= las[i]; // if(nx == -1) break; // // ok0 = ok1 = 1; // rep(i,60) if(las[i] == nx){ // if(now & (1LL << i)) ok1 = 0; // if(!(now & (1LL << i))) ok0 = 0; // } // if(ok0==ok1==0) wt(-1), break_continue; // if(ok0==0){ // res++; // now ^= (1LL << 60) - 1; // } // // cur = nx; // } // ok0 = ok1 = 1; // rep(i,60) if(las[i]==-1){ // if(now & (1LL << i)) ok0 = 0; // if(!(now & (1LL << i))) ok1 = 0; // } // if(ok0==ok1==0 || (str==1 && ok0==0)) wt(-1), continue; // if(ok0==0) res++; // wt(res); // } // }