fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <deque>
  4. #include <queue>
  5. #include <map>
  6. #include <set>
  7. #include <algorithm>
  8. #include <functional>
  9. #include <numeric>
  10. #include <iostream>
  11. #include <string>
  12. #include <cmath>
  13.  
  14. using namespace std;
  15. typedef long long ll;
  16. typedef unsigned int uint;
  17. typedef unsigned long long ull;
  18.  
  19. #define REP(i,n) for(int i = 0; i < (int)(n); ++i)
  20. #define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
  21. #define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
  22. #define ALL(c) (c).begin(), (c).end()
  23. #define SIZE(v) ((int)v.size())
  24. #define pb push_back
  25. #define mp make_pair
  26.  
  27. struct data {
  28.     vector<int> keys_i_have;
  29.     ull opened_chests; // 1がopened
  30.     vector<int> opened_order;
  31.     bool operator<(const data& right) const {
  32.         return opened_order.size() == right.opened_order.size() ?
  33.             opened_order > right.opened_order :
  34.             opened_order.size() > right.opened_order.size();
  35.     }
  36. };
  37.  
  38.  
  39. void print_vector( vector<int> &v ) {
  40.     for(int i = 0; i < v.size(); ++i){
  41.         // cerr << v[i] << ", ";
  42.     }
  43.     // cerr << endl;
  44. }
  45.  
  46. void print_data(data &d, int N){
  47.     // cerr << "-----" << endl;
  48.     // cerr << "keys: ";
  49.     print_vector( d.keys_i_have );
  50.     // cerr << "chests: ";
  51.     for(int i = 0; i < N; ++i){
  52.         // cerr << (bool)(d.opened_chests & (1 << i)) << ", ";
  53.     }
  54.     // cerr << endl;
  55.     // cerr << "order: ";
  56.     print_vector( d.opened_order );
  57.     // cerr << "-----" << endl;
  58. }
  59.  
  60. bool canOpen(int key, int c, vector<int> &needed_keys){
  61.     return (key == needed_keys[c]);
  62. }
  63.  
  64.  
  65.  
  66.  
  67. vector<int> dfs(vector<int>& needed_keys,
  68.                 vector<vector<int> >& inside_keys,
  69.                 int N,
  70.                 map< ull, char >& seen,
  71.                 data& d
  72.     )
  73. {
  74.     print_data(d, N);
  75.  
  76.  
  77.     // all chests are opened
  78.     // cerr << "order_size = " << d.opened_order.size() << ", N = " << N << endl;
  79.  
  80.  
  81.     // 途中で同じ状態が出てきた場合→終了
  82.     if (seen.count( d.opened_chests ) != 0){
  83.         // cerr << "skip." << endl;
  84.         return vector<int>();
  85.     }
  86.     seen[ d.opened_chests ] = 1;
  87.  
  88.     // キーがひとつもない場合→終了
  89.     if (d.keys_i_have.size() == 0){
  90.         // cerr << "no key. quit." << endl;
  91.         return vector<int>();
  92.     }
  93.  
  94.     // 開けられる棚を一つずつ開ける
  95.     for(int c = 0; c < N; ++c){
  96.  
  97.         // まだ開けていない
  98.         if (!(d.opened_chests & (1 << c))){
  99.  
  100.             // 棚を開けるのに必要な鍵
  101.             int key = needed_keys[c];
  102.  
  103.             // 手持ちの鍵であけることができるかどうか調べる
  104.             int key_index = -1;
  105.             for(int k = 0; k < d.keys_i_have.size(); ++k){
  106.                 if (d.keys_i_have[k] == key){
  107.                     key_index = k;
  108.                     break;
  109.                 }
  110.             }
  111.  
  112.             //　もし開けることができるなら
  113.             if ( key_index != -1 ){
  114.                 // cerr << "i can open chest %d." << endl;
  115.  
  116.                 vector<int> keys_i_have_refresh = d.keys_i_have;
  117.                 keys_i_have_refresh.erase( keys_i_have_refresh.begin() + key_index );
  118.  
  119.                 data next = d;
  120.                 next.keys_i_have = keys_i_have_refresh;
  121.  
  122.                 // 棚が空いた
  123.                 next.opened_chests |= (1 << c);
  124.                 // 棚が空いたことにより鍵が増える
  125.                 for(int k2 = 0; k2 < inside_keys[c].size(); ++k2){
  126.                     next.keys_i_have.push_back( inside_keys[c][k2] );
  127.                 }
  128.                 // 棚の順番を記録
  129.                 next.opened_order.push_back( c );
  130.  
  131.  
  132.                 // end?
  133.                 if (next.opened_order.size() == N){
  134.                     // cerr << "done!" << endl;
  135.                     vector<int> ret;
  136.                     ret.push_back( c );
  137.                     return ret;
  138.                 }
  139.                 else{
  140.                     vector<int> dfs_ret = dfs(needed_keys,
  141.                                               inside_keys,
  142.                                               N,
  143.                                               seen,
  144.                                               next);
  145.                     //// cerr << "dfs_ret = " << endl;
  146.                     //print_vector( dfs_ret );
  147.                     //// cerr << "d.opned_order = " << endl;
  148.                     //print_vector( d.opened_order );
  149.  
  150.  
  151.                     if (dfs_ret.size() != 0){
  152.                         vector<int> ret;
  153.                         ret.push_back(c);
  154.                         ret.insert(ret.end(), dfs_ret.begin(), dfs_ret.end());
  155.                         // cerr << "i can open the remain chests!" << endl;
  156.                         return ret;
  157.                     }
  158.                     else{
  159.                         // cerr << "i cannot open the remain chests.." << endl;
  160.                     }
  161.                 }
  162.             }
  163.         }
  164.     }
  165.     return vector<int>();
  166. }
  167.  
  168. int main(void)
  169. {
  170.     int T;
  171.     cin >> T;
  172.  
  173.     for(int t = 0; t < T; ++t){
  174.         int K, N;
  175.         cin >> K >> N;
  176.         vector<int> keys_i_have(K);
  177.         for(int k = 0; k < K; ++k){
  178.             cin >> keys_i_have[k];
  179.             --keys_i_have[k];
  180.         }
  181.         vector<int> needed_keys(N);
  182.         vector<vector<int> > inside_keys(N);
  183.         for(int n = 0; n < N; ++n){
  184.             cin >> needed_keys[n];
  185.             --needed_keys[n];
  186.             int inside_key_num;
  187.             cin >> inside_key_num;
  188.             inside_keys[n].resize(inside_key_num);
  189.             for(int i = 0; i < inside_key_num; ++i){
  190.                 cin >> inside_keys[n][i];
  191.                 --inside_keys[n][i];
  192.             }
  193.         }
  194.  
  195.  
  196.         // 状態は、持っている鍵と、あけた箱
  197.         priority_queue<data> q;
  198.         data ini;
  199.         ini.keys_i_have = keys_i_have;
  200.         ini.opened_chests = 0u;
  201.         q.push(ini);
  202.         map< ull, char > seen;
  203.  
  204.         vector<int>ans = dfs(needed_keys, inside_keys, N, seen, ini);
  205.  
  206.         if (!ans.size()){
  207.             cout << "Case #" << (t+1) << ": IMPOSSIBLE" << endl;
  208.         }
  209.         else{
  210.             cout << "Case #" << (t+1) << ": ";
  211.             FOREACH(i, ans){
  212.                 cout << (*i+1) << " ";
  213.             }
  214.             cout << endl;
  215.         }
  216.     }
  217.  
  218.     return 0;
  219. }
  220.  
Success #stdin #stdout 0s 3048KB
comments (?)
stdin
copy 
3
1 4
1
1 0
1 2 1 3
2 0
3 1 2
3 3
1 1 1
1 0
1 0
1 0
1 1
2
1 1 1
stdout
copy 
Case #1: 2 1 4 3 
Case #2: 1 2 3 
Case #3: IMPOSSIBLE
https://ideone.com/ug0h6V
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!