結果

問題 No.5002 stick xor
ユーザー どららどらら
提出日時 2018-05-30 01:27:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 984 ms / 1,000 ms
コード長 7,316 bytes
コンパイル時間 37,425 ms
実行使用メモリ 1,732 KB
スコア 41,939
最終ジャッジ日時 2018-05-30 01:28:17
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 984 ms
1,724 KB
testcase_01 AC 983 ms
1,728 KB
testcase_02 AC 984 ms
1,732 KB
testcase_03 AC 983 ms
1,724 KB
testcase_04 AC 984 ms
1,724 KB
testcase_05 AC 984 ms
1,728 KB
testcase_06 AC 984 ms
1,724 KB
testcase_07 AC 984 ms
1,724 KB
testcase_08 AC 984 ms
1,728 KB
testcase_09 AC 984 ms
1,724 KB
testcase_10 AC 983 ms
1,724 KB
testcase_11 AC 984 ms
1,728 KB
testcase_12 AC 983 ms
1,724 KB
testcase_13 AC 984 ms
1,728 KB
testcase_14 AC 983 ms
1,728 KB
testcase_15 AC 983 ms
1,724 KB
testcase_16 AC 984 ms
1,728 KB
testcase_17 AC 984 ms
1,728 KB
testcase_18 AC 984 ms
1,724 KB
testcase_19 AC 984 ms
1,728 KB
testcase_20 AC 983 ms
1,728 KB
testcase_21 AC 984 ms
1,728 KB
testcase_22 AC 984 ms
1,728 KB
testcase_23 AC 983 ms
1,728 KB
testcase_24 AC 983 ms
1,724 KB
testcase_25 AC 983 ms
1,728 KB
testcase_26 AC 984 ms
1,728 KB
testcase_27 AC 984 ms
1,724 KB
testcase_28 AC 983 ms
1,724 KB
testcase_29 AC 984 ms
1,728 KB
testcase_30 AC 984 ms
1,728 KB
testcase_31 AC 984 ms
1,728 KB
権限があれば一括ダウンロードができます

ソースコード

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[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 t, int len, const vector<int>& parts, const vector<int>& prev, const vector<int>& next){
    double ret1 = 0, ret2 = 0;
    rep(i,len){
      if(t==0){
        if(parts[i]%2==0){
          ret1 += 1.0;
        }else{
          if(prev[i]%2==0 && next[i]%2==0) ret1 += 0.5;
          else ret1 -= 10.0;
        }
      }else{
        if(parts[i]%2==1){
          ret2 += 1.0;
        }else{
          if(prev[i]%2==1 && next[i]%2==1) ret2 += 0.5;
          else ret2 -= 10.0;
        }
      }
    }
    if(t==0) return ret1;
    return ret2;
  }

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

    vpos.clear();
    vector<int> prev(30,0);
    vector<int> parts(30,0);
    vector<int> next(30,0);

    const int TH = N*N*0.5;
    rep(t, K){
      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(t<TH, 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(t<TH, 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.push_back((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;
}
0