結果

問題 No.5002 stick xor
ユーザー iehniehn
提出日時 2018-05-26 15:31:46
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 6,227 bytes
コンパイル時間 37,007 ms
スコア 0
最終ジャッジ日時 2018-05-26 15:32:37
ジャッジサーバーID
（参考情報） 		judge9 /
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

// C++11
#define _DEBUG
#define DEBUG2
#define _DEBUG3
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cmath>
#include "bits/stdc++.h"
#include <sys/time.h>
#include <emmintrin.h>
#include <string>
#include <bitset>


using namespace std;

inline long long GetTSC() {
  long long lo, hi;
  asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
  return lo + (hi << 32);
}
inline double GetSeconds() {
  return GetTSC() / 2.8e9;
}

class XRand
{
  public:
    unsigned int x, y, z, w;
    const int DC = pow(2, 27);
    XRand() { init(); }
    void init() { x = 314159261; y = 358979323; z = 846264338; w = 327950288; }
    unsigned int next() { unsigned int t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8; }
    int nextInt(int m) { return (int)(next() % m); }
    double nextDouble() { return double(next() % DC) / DC; }
};

const double TO = 0.9;
const int NM = 60;
const int NMM = NM * NM;
const int KM = 500;
bitset<NMM> A;
bitset<NMM> mask[26][NMM * 2];
int mi[26];
int RI[KM];
int L[KM];
int R[KM][4];
double starttime, gt;
XRand rnd = XRand();

#ifdef DEBUG

struct XorShift {
  uint64_t x = 88172645463325252ULL;

  XorShift() {}

  void setSeed(uint64_t seed) {
    x = seed;
  }

  uint64_t next() {
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
  }

  int nextInt(int n) {
    uint64_t upper = 0xFFFFFFFFFFFFFFFFULL / n * n;
    uint64_t v = next();
    while (v >= upper) {
      v = next();
    }
    return v % n;
  }

  double nextDouble() {
    uint64_t v = next() >> 11; // 53bit
    return (double)v / (1ULL << 53);
  }
};

XorShift xs;

int p_seed;
bitset<NM*NM> p_a;
bitset<NM*NM> p_a_init;
int p_l[KM];

class PlayMachine {
  public:

    static void init(int i){
      p_seed = i;
      xs.setSeed(p_seed);
      p_a_init.reset();
      p_a.reset();
      for(int i=0; i<NMM; i++){
        p_a_init[i] = xs.nextInt(2);
      }
      for(int i=0; i<KM; i++){
        p_l[i] = xs.nextInt(25) + 1;
      }
    }

    static int calc_score(){
      p_a = p_a_init;
      for(int i=0; i<KM; i++){
        int a,b,c,d;
        a = R[i][0];
        b = R[i][1];
        c = R[i][2];
        d = R[i][3];
        int l = p_l[i];
        if((a == c && d-b+1 == l) || (b == d && c-a+1 == l)){
          for(int j=a; j<=c; j++){
            for(int k=b; k<=d; k++){
              p_a[j*NM+k] = 1 - p_a[j*NM+k];
            }
          }
        }else{
          cout << "err i: " << i << " l: " << l << " a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
        }
      }
      cout << p_seed << " "  << (p_a_init.count() - p_a.count()) << endl;
      return p_a_init.count() - p_a.count();
    }

    static void print(){
      int score = calc_score();
#ifdef DEBUG2
      cerr << "60 500" << endl;
      for(int i=0; i<KM; i++){
        cerr << p_l[i] << " ";
      }
      cerr << endl;
      cerr << endl;
      for(int i=0; i<NM; i++){
        for(int j=0; j<NM; j++){
          cerr << p_a_init[i*NM+j];
        }
        cerr << endl;
      }
      cerr << endl;
      for(int i=0; i<NM; i++){
        for(int j=0; j<NM; j++){
          cerr << p_a[i*NM+j];
        }
        cerr << endl;
      }
      cerr << endl;
#endif
      cerr << "score: " << score << endl;
    }
};
#endif

void solve(){
  starttime = GetSeconds();

  // input
#ifdef DEBUG
  A = p_a_init;
  for(int i=0; i<KM; i++){
    L[i] = p_l[i];
  }
#else
  int n,k;
  cin >> n >> k;
  for(int i=0; i<k; i++){
    cin >> L[i];
  }
  for(int i=0; i<n; i++){
    string s;
    cin >> s;
    for(int j=0; j<n; j++){
      A[i*NM+j] = s[j] == '1';
    }
  }
#endif

  // init
  for(int i=1; i<26; i++){
    mi[i] = 0;
    auto ma = mask[i];
    for(int j=0; j<NM; j++){
      for(int k=0; k<NM; k++){
        if(j <= NM-i){
          ma[mi[i]].reset();
          for(int l=0; l<i; l++){
            ma[mi[i]][(j+l)*NM+k] = 1;
          }
          mi[i]++;
        }
        if(k <= NM-i && i > 1){
          ma[mi[i]].reset();
          for(int l=0; l<i; l++){
            ma[mi[i]][j*NM+k+l] = 1;
          }
          mi[i]++;
        }
      }
    }
    ma[mi[i]].reset();
  }

  for(int l=25; l>0; l--){
    auto ma = mask[l];
    int mm = mi[l];
    for(int i=0; i<KM; i++){
      if(L[i] != l) continue;
      int ti = 0;
      int tm = -30;
      for(int j=0; j<mm; j++){
        int tc = (A & ma[j]).count();
        if(tc > tm){
          tm = tc;
          ti = j;
        }
      }
      RI[i] = ti;
      A ^= ma[RI[i]];
    }
  }

  int cc = A.count();
#ifdef DEBUG2
  cerr << "bcc: " << cc << endl;
#endif
  int tt = 0;
  while(1){
    double gt = (GetSeconds() - starttime) / TO;
    if(gt >= 1.0) break;
    int i = tt % KM;
    int l = L[i];
    int ri = RI[i];
    auto ma = mask[l];
    int mii = mi[l];
    int ni = rnd.nextInt(mii - 1);
    if(ni >= ri) ni++;
    int nc = (A ^ ma[ri] ^ ma[ni]).count();
    if(nc <= cc || rnd.nextDouble() / pow(nc - cc, 2) > gt){
      RI[i] = ni;
      cc = nc;
      A ^= ma[ri] ^ ma[ni];
    }else{
    }
    tt++;
  }
#ifdef DEBUG2
  cerr << "acc: " << cc << endl;
#endif

  // output
  for(int i=0; i<KM; i++){
    int l = L[i];
    int ri = RI[i];
    auto ms = mask[l][ri];
    for(int j=0; j<NMM; j++){
      if(!ms[j]) continue;
      R[i][0] = j / NM;
      R[i][1] = j % NM;
      R[i][2] = j / NM;
      R[i][3] = j % NM;
      if(j+1 < NMM && ms[j+1]) R[i][3] += l - 1;
      if(j+NM < NMM && ms[j+NM]) R[i][2] += l - 1;
      break;
    }
  }

  cerr << "tt: " << tt << ", time: " << (GetSeconds() - starttime) << endl;
}

#ifdef DEBUG
#ifdef DEBUG2
const int TEST_MAX = 1;
#else
const int TEST_MAX = 10;
#endif
int main() {
  srand((unsigned) time(NULL));
  double total = 0;
  for(int i=1; i<=TEST_MAX; i++){
#ifdef DEBUG2
    PlayMachine::init(10);
#else
    PlayMachine::init(i);
#endif
    solve();
#ifdef DEBUG2
    PlayMachine::print();
  }
#else
    int score = PlayMachine::calc_score();
    total += score;
  }
  cerr << "avg: " << total / TEST_MAX << endl;
#endif
  return 0;
}
#else
int main(){
  solve();
  for(int i=0; i<KM; i++){
    cout << R[i][0] + 1;
    for(int j=1; j<4; j++){
      cout << " " << R[i][j] + 1;
    }
    cout << endl;
  }
  return 0;
}
#endif
0