結果

問題 No.74 貯金箱の退屈
ユーザー myantamyanta
提出日時 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);
      |                         ~~~~~^~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0