結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
![]() |
提出日時 | 2017-05-29 04:15:10 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 1,403 bytes |
コンパイル時間 | 704 ms |
コンパイル使用メモリ | 61,272 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 17:59:42 |
合計ジャッジ時間 | 1,806 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:93:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 93 | scanf("%d", &d[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:108:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 108 | scanf("%d", &t); | ~~~~~^~~~~~~~~~
ソースコード
#include<cstdio>#include<vector>#include<set>using namespace std;using vi=vector<int>;using vvi=vector<vi>;using vu=vector<unsigned>;set<vu> h;void bit_set(vu& d, int b, int v){if(v) d[b/32]|=(1<<(b%32));else d[b/32]&=~(1<<(b%32));}int bit_get(vu& d, int b){return (d[b/32]>>(b%32))&1;}void bit_inv(vu& d, int b){bit_set(d, b, 1-bit_get(d, b));}void solve_i(vu& w, const vvi& ef, const vvi& eb, int& ret){int i, n=ef.size();vu ww;if(h.find(w)!=h.end()) return;if(ret) return;h.insert(w);for(i=0;i<n;i++){if(bit_get(w, i)==0) break;}if(i>=n){ret=1;return;}for(auto ebe:eb[i]){ww=w;for(auto efe:ef[ebe]){bit_inv(ww, efe);}solve_i(ww, ef, eb, ret);if(ret) break;}}int solve(vu& w, vvi& ef, vvi& eb){int ret=0;h.clear();solve_i(w, ef, eb, ret);return ret;}int main(void){int n, i, ni, pi;vi d;vvi ef, eb;vu w;while(scanf("%d", &n)==1){eb.clear();eb.resize(n);ef=eb;w.assign((n+31)/32, 0);d.resize(n);for(i=0;i<n;i++){scanf("%d", &d[i]);ni=(i+d[i])%n;pi=((i-d[i])%n+n)%n;ef[i].push_back(ni);eb[ni].push_back(i);if(ni!=pi){ef[i].push_back(pi);eb[pi].push_back(i);}}for(i=0;i<n;i++){int t;scanf("%d", &t);bit_set(w, i, t);}printf("%s\n", solve(w, ef, eb)?"Yes":"No");}return 0;}