naoya_t@topcoder

UAPC 2010 I. Mysterious Onslaught (みょんみょん問題) - サンプルは通るけどTLEが出る駄目コード

UAPC | 17:26 |

• とりあえず貼っとく

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  while(1){
    int n;cin>>n;if(!n)break;
    int m0=0;
    vector<int> masks;
    rep(y0,n){
      rep(x0,n){
        FOR(h,1,n-y0){
          FOR(w,1,n-x0){
            int m=0;
            rep(j,h){ int y=y0+j;
              rep(i,w){ int x=x0+i;
                m |= (1<<(y*n+x));
              }
            }
            masks.pb(m);
          }
        }
      }
    }
    int nmask=sz(masks);

    rep(y,n){
      rep(x,n){
        int z;cin>>z;
        if(z) m0 |= (1<<(y*n+x));
      }
    }

    set<int> visited;
    vector<int> q; q.pb(m0); visited.insert(m0);
    int here=0,step;
    for(step=1;;step++){
      int till=sz(q); if(till==here) break;
      for(int i=here; i<till; ++i){
        int mi=q[i], mic=__builtin_popcount(mi);
        rep(j,nmask){
          int mj=mi^masks[j];
          if(mj==0) goto ans;
          int mjc=__builtin_popcount(mj); if (mjc>mic) continue;
          if(!found(visited,mj)) {
            q.pb(mj); visited.insert(mj);
          }
        }
      }
      here=till;
    }
 ans:
    rep(i,step)cout<<"myon";cout<<endl;
  }
  return 0;
}