結果

問題 No.5002 stick xor
コンテスト
ユーザー どらら
提出日時 2018-05-26 20:39:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 987 ms / 1,000 ms
コード長 4,504 bytes
コンパイル時間 36,500 ms
実行使用メモリ 1,728 KB
スコア 40,307
最終ジャッジ日時 2018-05-26 20:39:42
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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[2] = {1,0};
  const int vy[2] = {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;

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

    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;
  }

  inline double calcTemp(double sec, double time_limit){
    double start_temp = 1.0;
    double end_temp = 0.001;
    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;
      rep(i,L[si]){
        if(A[y][x]%2==0) score--;
        else score++;
        A[y][x]--;
        x += vx[a.a];
        y += vy[a.a];
      }
    }
    {
      int x = b.x;
      int y = b.y;
      rep(i,L[si]){
        A[y][x]++;
        if(A[y][x]%2==0) score++;
        else score--;
        x += vx[b.a];
        y += 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(){
    init();

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

      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(A[y][x]%2==0){
          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%1000==0) cerr << "\r" << T << "\t\t" << score-base_score << "\t\t" << acnt/(double)cnt;
    }
    cerr << "last score: " << best_score-base_score << endl;
    cerr << "loop count: " << cnt << 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;
}
0