結果
問題 |
No.74 貯金箱の退屈
|
ユーザー |
![]() |
提出日時 | 2014-11-21 00:40:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,660 bytes |
コンパイル時間 | 887 ms |
コンパイル使用メモリ | 76,124 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-02 19:45:26 |
合計ジャッジ時間 | 4,953 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 RE * 2 |
other | RE * 30 |
コンパイルメッセージ
main.cpp: In function ‘bool reverse_coin(std::string&, int)’: main.cpp:35:1: warning: no return statement in function returning non-void [-Wreturn-type] 35 | } | ^
ソースコード
#include<iostream> #include<string> #include<map> #include<vector> using namespace std; template<typename Iterator> bool is_all1(Iterator begin,Iterator end) { for(Iterator itr = begin;itr!=end;++itr) { if(*itr=='0'){ return false; } } return true; } template<typename Iterator> void dump(Iterator begin,Iterator end) { for(Iterator itr = begin;itr!=end;++itr) { cout << *itr << ","; } cout << endl; } bool reverse_coin(string& s,int index) { if(s[index]=='0'){ s[index]='1'; }else{ s[index]='0'; } } bool solve(const vector<int>& coins,string coin_state,map<string,int>& pattern) { //dump(coin_state.begin(),coin_state.end()); if(is_all1(coin_state.begin(),coin_state.end())) { return true; } if(pattern[coin_state]) { return false; } pattern[coin_state]=true; for(int i=0;i<coins.size();i++) { int a = (i+coins[i])%coins.size(); int b = (i-coins[i]+coins.size())%coins.size(); if(a==b) { reverse_coin(coin_state,a); if(solve(coins,coin_state,pattern)) return true; reverse_coin(coin_state,a); } else { reverse_coin(coin_state,a); reverse_coin(coin_state,b); if(solve(coins,coin_state,pattern)) return true; reverse_coin(coin_state,a); reverse_coin(coin_state,b); } } return false; } int main() { int n; vector<int> coins; cin >> n; string coin_state; for(int i=0;i<n;i++) { int d; cin >> d; coins.push_back(d); } for(int i=0;i<n;i++) { int w; cin >> w; coin_state+=w+'0'; } map<string,int> pattern; cout << (solve(coins,coin_state,pattern)?"Yes":"No") << endl; }