#262112 (C++14) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: どらら
• 提出日時: 2018-06-01 22:58:13
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 985 ms / 1,000 ms
• コード長: 7,583 bytes
• コンパイル時間: 35,925 ms
• 実行使用メモリ: 1,748 KB
• スコア: 42,311
• 最終ジャッジ日時: 2018-06-01 22:58:52
• ジャッジサーバーID （参考情報）: judge8 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	984 ms; 1,744 KB
testcase_01	AC	984 ms; 1,744 KB
testcase_02	AC	984 ms; 1,744 KB
testcase_03	AC	984 ms; 1,744 KB
testcase_04	AC	984 ms; 1,748 KB
testcase_05	AC	985 ms; 1,744 KB
testcase_06	AC	985 ms; 1,744 KB
testcase_07	AC	984 ms; 1,744 KB
testcase_08	AC	983 ms; 1,744 KB
testcase_09	AC	985 ms; 1,748 KB
testcase_10	AC	984 ms; 1,744 KB
testcase_11	AC	985 ms; 1,744 KB
testcase_12	AC	984 ms; 1,740 KB
testcase_13	AC	985 ms; 1,744 KB
testcase_14	AC	984 ms; 1,744 KB
testcase_15	AC	984 ms; 1,744 KB
testcase_16	AC	985 ms; 1,748 KB
testcase_17	AC	984 ms; 1,744 KB
testcase_18	AC	985 ms; 1,748 KB
testcase_19	AC	985 ms; 1,748 KB
testcase_20	AC	983 ms; 1,744 KB
testcase_21	AC	984 ms; 1,744 KB
testcase_22	AC	985 ms; 1,748 KB
testcase_23	AC	985 ms; 1,748 KB
testcase_24	AC	984 ms; 1,740 KB
testcase_25	AC	985 ms; 1,740 KB
testcase_26	AC	984 ms; 1,748 KB
testcase_27	AC	984 ms; 1,748 KB
testcase_28	AC	984 ms; 1,744 KB
testcase_29	AC	984 ms; 1,740 KB
testcase_30	AC	985 ms; 1,748 KB
testcase_31	AC	983 ms; 1,748 KB

ソースコード

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

unsigned int xor128(){
  static unsigned int x=123456789, y=362436069, z=521288629, w=88675123;
  unsigned int t;
  t=(x^(x<<11));
  x=y; y=z; z=w;
  return w=(w^(w>>19))^(t^(t>>8));
}
inline double frand(){
  return xor128()%UINT_MAX/static_cast<double>(UINT_MAX);
}

class Timer {
  double start_time;
  double get_now(){
    struct timeval t;
    gettimeofday(&t, NULL);
    return t.tv_sec + t.tv_usec * 1e-6;
  }
public:
  void start(){
    start_time = get_now();
  }
  double sec(){
    return get_now()-start_time;
  }
};


class Solver5002 {
  Timer timer;
  const double time_limit = 0.98;
  //const double time_limit = 9.5;

  const int vx[4] = {1,0,-1,0};
  const int vy[4] = {0,1,0,-1};

  struct POS {
    int y, x, a;
  };

  int N, K;
  vector<int> L;
  vector<vector<int>> A;

  double base_score, score, best_score;
  vector<POS> vpos, best_vpos;


  double iscore(int len, const vector<int>& parts, const vector<int>& prev, const vector<int>& next){
    double ret = 0;
    rep(i,len){
      if(parts[i]%2==1){
        ret += 1.0;
      }else{
        if(prev[i]%2==1 && next[i]%2==1) ret += 0.5;
        else ret -= 10.0;
      }
    }
    return ret;
  }

  void init(){
    base_score = 0;
    rep(y,N){
      rep(x,N){
        if(A[y][x]%2==0) base_score++;
      }
    }

    vector<int> lenp;

    map<int,vector<int>> lenm;
    rep(i,K) lenm[L[i]].push_back(i);
    FOR(it,lenm){
      if(it->first > 2) continue;
      rep(i,(it->second).size()){
        lenp.push_back((it->second)[i]);
      }
      (it->second).clear();
    }
    while(true){
      bool flg = true;
      FOR(it,lenm){
        if((it->second).size() > 0){
          lenp.push_back((it->second).back());
          (it->second).pop_back();
          flg = false;
        }
      }
      if(flg) break;
    }
    reverse(ALLOF(lenp));


    vpos = vector<POS>(K);
    vector<int> prev(30,0);
    vector<int> parts(30,0);
    vector<int> next(30,0);
    rep(tt, K){
      int t = lenp[tt];
      double best_score = -1e18;
      int best_y = 0, best_x = 0, which = 0;
      rep(y,N){
        rep(x,N){
          if(x+L[t]<N){
            rep(i,L[t]){
              parts[i] = A[y][x+i];
              if(y-1>=0) prev[i] = A[y-1][x+i];
              else prev[i] = parts[i];
              if(y+1<N) next[i] = A[y+1][x+i];
              else next[i] = parts[i];
            }
            double d = iscore(L[t], parts, prev, next);
            if(best_score <= d){
              best_score = d;
              best_y = y;
              best_x = x;
              which = 0;
            }
          }
          if(y+L[t]<N){
            rep(i,L[t]){
              parts[i] = A[y+i][x];
              if(x-1>=0) prev[i] = A[y+i][x-1];
              else prev[i] = parts[i];
              if(x+1<N) next[i] = A[y+i][x+1];
              else next[i] = parts[i];
            }
            double d = iscore(L[t], parts, prev, next);
            if(best_score <= d){
              best_score = d;
              best_y = y;
              best_x = x;
              which = 1;
            }
          }
        }
      }

      {
        int ra = which;
        int x = best_x;
        int y = best_y;
        vpos[t] = (POS){y,x,ra};
        rep(j,L[t]){
          A[y][x]++;
          x += vx[ra];
          y += vy[ra];
        }
      }
    }
    /*
    vpos.clear();
    rep(i,K){
      int ra = xor128()%2;
      int W = N - vx[ra]*(L[i]-1);
      int H = N - vy[ra]*(L[i]-1);
      int x = xor128()%W;
      int y = xor128()%H;
      vpos.push_back((POS){y,x,ra});
      rep(j,L[i]){
        A[y][x]++;
        x += vx[ra];
        y += vy[ra];
      }
    }
    */
    score = 0;
    rep(y,N){
      rep(x,N){
        if(A[y][x]%2==0) score++;
      }
    }
    best_score = score;
    best_vpos = vpos;
    cerr << "initial score = " << score << " " << base_score << " " << score - base_score << endl;
  }

  inline double calcTemp(double sec, double time_limit){
    double start_temp = 0.1;
    double end_temp = 0.0001;
    double now_temp = start_temp + (end_temp - start_temp) * sec / time_limit;
    return now_temp;
  }

  inline void pswap(int si, const POS& a, const POS& b){
    {
      int x = a.x;
      int y = a.y;
      int w = b.x;
      int z = b.y;
      rep(i,L[si]){
        if(A[y][x]%2==0){
          score--;
        }else{
          score++;
        }
        A[y][x]--;

        A[z][w]++;
        if(A[z][w]%2==0){
          score++;
        }else{
          score--;
        }

        x += vx[a.a];
        y += vy[a.a];
        w += vx[b.a];
        z += vy[b.a];
      }
    }
    vpos[si] = b;
  }

public:
  Solver5002(int N, int K):
  N(N),
  K(K),
  L(K,0),
  A(N,vector<int>(N,0))
  {
    timer.start();
  }

  void setL(int i, int v){ L[i] = v; }
  void setA(int i, int j, int v){ A[i][j] = v; }

  void solve(){
    cerr << timer.sec() << endl;
    init();
    double start_sec = timer.sec();
    cerr << start_sec << endl;

    int cnt = 0;
    int acnt = 0;
    while(true){
      double sec = timer.sec();
      if(sec > time_limit) break;
      double T = calcTemp(sec-start_sec, time_limit-start_sec);

      cnt++;
      int prev_score = score;
      int si = xor128()%K;
      POS pos = vpos[si];
      POS npos;
      {
        int ra = xor128()%2;
        //int ra = cnt%2;
        int W = N - vx[ra]*(L[si]-1);
        int H = N - vy[ra]*(L[si]-1);
        int x = xor128()%W;
        int y = xor128()%H;
        /*
        while(true){
          if(A[y][x]%2==1) break;
          else{
            int cnt = 0;
            rep(k,2){
              int nx = x + vx[(2*k+ra)%4];
              int ny = y + vy[(2*k+ra)%4];
              if(0<=nx && nx<N && 0<=ny && ny<N){
                if(A[y][x]%2==1) cnt++;
              }
            }
            if(cnt>=1) break;
          }
          x = xor128()%W;
          y = xor128()%H;
        }
        */
        npos.x = x;
        npos.y = y;
        npos.a = ra;
      }

      pswap(si, pos, npos);

      double delta = (score - prev_score);
      if(delta >= 0){
        //acnt++;
      }else{
        if(exp(delta / T) >= frand()){
          //acnt++;
        }else{
          pswap(si, npos, pos);
        }
      }
      if(best_score < score){
        best_score = score;
        best_vpos = vpos;
      }
      //if(cnt%100==0) cerr << T << "\t\t" << score-base_score << "\t\t" << acnt/(double)cnt << endl;;
    }
    cerr << "last score: " << best_score-base_score << endl;
    cerr << "loop count: " << cnt << endl;
/*
    rep(y,N){
      rep(x,N){
        cerr << A[y][x] << " ";
      }
      cerr << endl;
    }
*/
  }

  void output(){
    rep(i,K){
      cout << best_vpos[i].y+1 << " ";
      cout << best_vpos[i].x+1 << " ";
      cout << best_vpos[i].y+1+vy[best_vpos[i].a]*(L[i]-1) << " ";
      cout << best_vpos[i].x+1+vx[best_vpos[i].a]*(L[i]-1) << endl;
    }
  }
};


int main(){
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;

  Solver5002 solver(N, K);
  rep(i,K){
    int l;
    cin >> l;
    solver.setL(i, l);
  }
  vector<string> A;
  rep(i,N){
    string a;
    cin >> a;
    rep(j,N){
      if(a[j] == '0') solver.setA(i, j, 0);
      else solver.setA(i, j, 1);
    }
  }

  solver.solve();
  solver.output();

  return 0;
}