Facebook
From emanlaicepsa, 1 Month ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 41
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("Ofast,unroll-loops")
  3. #pragma GCC target("avx,avx2,sse,sse2,sse3,fma")
  4. using namespace std;
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define pb emplace_back
  9. #define all(n) (n).begin(),(n).end()
  10. #define mem(n,x) memset(n,x,sizeof(n))
  11. #define IOS ios::sync_with_stdio(0),cin.tie(0)
  12. #define pii pair<ll,ll>
  13. #define vi vector<ll>
  14. #define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
  15. template<typename A> void _do(A x){ cerr<<x<<"\n"; }
  16. template<typename A, typename ...B> void _do(A x, B ...y){ cerr<<x<<", "; _do(y...);}
  17.  
  18. int n;
  19. vi cans, cur;
  20. bitset<75> cover[75];
  21. bool E[75][75];
  22. vi v(75);
  23.  
  24. void init(){
  25.         for(int i=0;i<n;i++) cover[i].reset();
  26.         for(int i=0;i<n;i++) for(int j=0;j<n;j++) E[i][j] = 0;
  27.         cans.clear(); cur.clear();
  28.         for(int i=0;i<n;i++) v[i] = 0;
  29. }
  30.  
  31. void dfs(int num, int cur, bitset<75> b){
  32.         /* for(auto i:v) cout<<i<<" "; cout<<'\n'; */
  33.         if((int)b.count() == n){
  34.                 /* dbg(num, cur, b.count(), v.size()); */
  35.                 if(num < (int)cans.size() || cans.empty()){
  36.                         cans.resize(num);
  37.                         for(int i=0;i<num;i++) cans[i] = v[i];
  38.                 }
  39.                 return;
  40.         }
  41.         if(num == 5) return;
  42.         for(int i=cur;i<n;i++){
  43.                 v[num] = i;
  44.                 dfs(num+1, i+1, b | cover[i]);
  45.         }
  46. }
  47.  
  48. void solve(){
  49.         char c;
  50.         for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>c, E[i][j] = c-'0';
  51.         for(int i=0;i<n;i++){
  52.                 for(int j=0;j<n;j++){
  53.                         if(i==j || E[i][j]) cover[i][j] = 1;
  54.                 }
  55.         }
  56.         bitset<75> b;
  57.         dfs(0, 0, b);
  58.         cout<<cans.size()<<" ";
  59.         for(auto &i:cans) cout<<i+1<<" ";
  60.         cout<<'\n';
  61. }
  62.  
  63. signed main(){
  64.         IOS;
  65.         int kas = 0;
  66.         while(cin>>n){
  67.                 init();
  68.                 cout<<"Case "<<++kas<<": ";
  69.                 solve();
  70.         }
  71.  
  72. }
  73.  
  74.