結果

問題 No.74 貯金箱の退屈
コンテスト
ユーザー myanta
提出日時 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;
}
0