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

• 問題: No.5002 stick xor
• ユーザー: iehn
• 提出日時: 2018-05-26 16:20:18
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 933 ms / 1,000 ms
• コード長: 6,268 bytes
• コンパイル時間: 34,127 ms
• 実行使用メモリ: 64,228 KB
• スコア: 38,091
• 最終ジャッジ日時: 2018-05-26 16:20:54
• ジャッジサーバーID （参考情報）: judge9 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	929 ms; 64,224 KB
testcase_01	AC	929 ms; 64,224 KB
testcase_02	AC	929 ms; 64,228 KB
testcase_03	AC	929 ms; 64,228 KB
testcase_04	AC	929 ms; 64,224 KB
testcase_05	AC	928 ms; 64,224 KB
testcase_06	AC	929 ms; 64,224 KB
testcase_07	AC	929 ms; 64,228 KB
testcase_08	AC	929 ms; 64,224 KB
testcase_09	AC	929 ms; 64,224 KB
testcase_10	AC	929 ms; 64,228 KB
testcase_11	AC	929 ms; 64,228 KB
testcase_12	AC	929 ms; 64,228 KB
testcase_13	AC	929 ms; 64,228 KB
testcase_14	AC	929 ms; 64,228 KB
testcase_15	AC	931 ms; 64,228 KB
testcase_16	AC	933 ms; 64,228 KB
testcase_17	AC	929 ms; 64,228 KB
testcase_18	AC	929 ms; 64,224 KB
testcase_19	AC	929 ms; 64,228 KB
testcase_20	AC	929 ms; 64,228 KB
testcase_21	AC	929 ms; 64,228 KB
testcase_22	AC	929 ms; 64,224 KB
testcase_23	AC	929 ms; 64,228 KB
testcase_24	AC	928 ms; 64,224 KB
testcase_25	AC	930 ms; 64,224 KB
testcase_26	AC	929 ms; 64,228 KB
testcase_27	AC	929 ms; 64,224 KB
testcase_28	AC	929 ms; 64,228 KB
testcase_29	AC	928 ms; 64,228 KB
testcase_30	AC	929 ms; 64,224 KB
testcase_31	AC	932 ms; 64,224 KB

ソースコード

// 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.85;
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 += rnd.nextInt(2) + 1){
      if(L[i] != l) continue;
      int ti = 0;
      int tm = -30;
      for(int j=0; j<mm; j += rnd.nextInt(2) + 1){
        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