#261348 (C++11) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: yowa
• 提出日時: 2018-05-29 14:35:58
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 470 ms / 1,000 ms
• コード長: 9,400 bytes
• コンパイル時間: 16,011 ms
• 実行使用メモリ: 1,580 KB
• スコア: 44,293
• 最終ジャッジ日時: 2018-05-29 14:36:16
• ジャッジサーバーID （参考情報）: judge6 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	429 ms; 1,580 KB
testcase_01	AC	407 ms; 1,580 KB
testcase_02	AC	420 ms; 1,576 KB
testcase_03	AC	469 ms; 1,576 KB
testcase_04	AC	409 ms; 1,580 KB
testcase_05	AC	406 ms; 1,580 KB
testcase_06	AC	420 ms; 1,580 KB
testcase_07	AC	447 ms; 1,580 KB
testcase_08	AC	415 ms; 1,576 KB
testcase_09	AC	416 ms; 1,580 KB
testcase_10	AC	470 ms; 1,576 KB
testcase_11	AC	417 ms; 1,580 KB
testcase_12	AC	419 ms; 1,580 KB
testcase_13	AC	464 ms; 1,580 KB
testcase_14	AC	414 ms; 1,580 KB
testcase_15	AC	405 ms; 1,576 KB
testcase_16	AC	466 ms; 1,576 KB
testcase_17	AC	411 ms; 1,580 KB
testcase_18	AC	417 ms; 1,580 KB
testcase_19	AC	463 ms; 1,580 KB
testcase_20	AC	404 ms; 1,580 KB
testcase_21	AC	413 ms; 1,576 KB
testcase_22	AC	435 ms; 1,576 KB
testcase_23	AC	435 ms; 1,576 KB
testcase_24	AC	408 ms; 1,576 KB
testcase_25	AC	411 ms; 1,580 KB
testcase_26	AC	463 ms; 1,576 KB
testcase_27	AC	419 ms; 1,580 KB
testcase_28	AC	433 ms; 1,576 KB
testcase_29	AC	458 ms; 1,576 KB
testcase_30	AC	414 ms; 1,576 KB
testcase_31	AC	407 ms; 1,580 KB

ソースコード

#include <iostream>
#include <cstdlib>

#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include "sys/time.h"
using namespace std;
#define HERE (cerr << "LINE: " << __LINE__ << " " << __FUNCTION__ << endl)

typedef long long ll_t;
typedef unsigned long long ull_t;

#define DBG(x) cerr << #x << ": " << x << endl

struct timeval timer_begin, timer_end;
int timer_called;
inline void timer_start() 
{
  timer_called++;
  gettimeofday(&timer_begin, NULL);    
}     
inline double timer_now() 
{         
  timer_called++;
  gettimeofday(&timer_end, NULL);         
  return timer_end.tv_sec - timer_begin.tv_sec +
    (timer_end.tv_usec - timer_begin.tv_usec)/1000000.0;     
}

template<class T>
const T& clamp(const T& v,const T& lo,const T& hi) {
  return (v < lo) ? lo : (v > hi) ? hi : v;
}
template<typename T>
void assign_min_max(T& min,T& max,const T& x) {
  if (x < min)
    min = x;
  if (x > max)
    max = x;
}
unsigned int hash_function(unsigned long p) {
  // xor32()
  p ^= p<<7;
  p ^= p>>1;
  p ^= p<<25;
  unsigned int c = __builtin_popcount(p);
  return p<<c | p>>(32-c);
}
uint64_t hash_function64(uint64_t p) {
  // xor64()
  p ^= p<<16;
  p ^= p>>7;
  p ^= p<<39;
  uint64_t c = __builtin_popcount(p);
  return p<<c | p>>(64-c);
}  

struct xor128_t {
  uint64_t x, y, z, w;

  xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
    for (int i=0; i<48; i++)
      get();
  }

  void init(int seed) {
    x = 123456789^seed;
    y = 362436069;
    z = 521288629;
    w = 88675123;

    for (int i=0; i<48; i++)
      get();
  }

  inline uint64_t get() {
    uint64_t t=(x^(x<<11)); x=y; y=z; z=w;
    return (w=(w^(w>>19))^(t^(t>>8)));
  }

  inline uint64_t get(unsigned int sz) {
    if (sz <= 1)
      return 0;

    uint64_t x;
    const uint64_t mask = (1<<(ilogb(sz-1)+1)) - 1;
    //cout << sz << " " << mask << endl;
    assert(mask >= (sz-1) && mask < 2*sz-1);
    do {
      x = get() & mask;
    } while (x >= sz);

    return x;
  }

  inline int64_t get(int beg,int end) {
    return get(end-beg) + beg;
  }

  double get_double() {
    static const double double_factor = 1.0 / (1.0 + 0xffffffffffffffffuLL);
    return get() * double_factor;
  }

  double get_norm() {
    double a = get_double();
    double b = get_double();

    return sqrt(-2*log(a)) * cos(2*M_PI*b);
  }

  double get_gamma(double a) {
    if (a < 1.0) {
      return get_gamma(1+a) * pow(get_double(), 1/a);
    }
    
    double d = a - 1/3.0;
    double c = 1/sqrt(9.0 * d);

    while (true) {
      double x = get_norm();
      double uni = 1 - get_double();
      double v = (1.0+c*x)*(1.0+c*x)*(1.0+c*x);
      if (v > 0 && log(uni) < 0.5 * x*x + d - d*v + d*log(v))
	return d*v;
    }
  }

  template<typename T> void shuffle(vector<T>& v,int partial=-1) {
    int sz = v.size();
    if (partial < 0 || partial > sz)
      partial = sz;

    for (int i=0; i<partial; i++) {
      swap(v[i], v[i + get(sz-i)]);
    }

  }
};

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[ ";
  for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " ]"; 
  return os; 
}
template<typename T> ostream& operator<<(ostream& os, const set<T>& v) {
  os << "{ ";
  for(typename set<T>::const_iterator it=v.begin(); it!=v.end(); ++it) {
    if (it != v.begin())
      os << ", ";
    os << *it; 
  }
  os << " }"; 
  return os; 
}
template<typename T1,typename T2> ostream& operator<<(ostream& os, const pair<T1,T2>& v) {
  os << "[ " << v.first << ", " << v.second << "]";
  return os; 
}

#ifdef LOCAL
double TIME_LIMIT_FACTOR = 0.55;
#else
double TIME_LIMIT_FACTOR = 1.0;
#endif
double TIME_LIMIT = TIME_LIMIT_FACTOR * 10.0;

/* insert here */
int N, K;

struct op_t {
  int x, y, L, d;
  op_t() {}
  op_t(int x,int y,int L,int d) : x(x), y(y), L(L), d(d) {}
  vector<int> to_v() const {
    if (d == 0) 
      return {y+1, x+1, y+1, x+L};
    else
      return {y+1, x+1, y+L, x+1};
  }

  bool is_valid() const {
    if (d == 0)
      return (x >= 0 && x < N-L+1 && y >= 0 && y < N);
    else
      return (x >= 0 && x < N && y >= 0 && y < N-L+1);      
  }
};

void apply(vector<string>& A,const op_t op) {
  if (op.d == 0) {
    for (int i=0; i<op.L; i++)
      A[op.y][op.x+i] ^= 1;
  } else {
    for (int i=0; i<op.L; i++)
      A[op.y+i][op.x] ^= 1;
  }
}

int evaluate(vector<string>& A,const op_t op) {
  const int w_black = 1;
  const int w_align = 2;
  const int w_border = 0;
  const int w_end = 1;

  int bb = 0;
  int c = 0;
  if (op.d == 0) {
    c += w_end*(A[op.y][op.x] & 1);
    c += w_end*(A[op.y][op.x+op.L-1] & 1);
    
    for (int i=0; i<op.L; i++) {
      c += w_black*(A[op.y][op.x+i] & 1);
      c += w_border*(i > 0 && A[op.y][op.x+i] != A[op.y][op.x+i-1]);
    }
    c += w_align*(op.x == 0 || A[op.y][op.x-1] != A[op.y][op.x]);
    c += w_align*(op.x+op.L == N || A[op.y][op.x+op.L] != A[op.y][op.x+op.L-1]);
  } else {
    c += w_end*(A[op.y][op.x] & 1);
    c += w_end*(A[op.y+op.L-1][op.x] & 1);
    
    for (int i=0; i<op.L; i++) {
      c += w_black*(A[op.y+i][op.x] & 1);
      c += w_border*(i > 0 && A[op.y+i][op.x] != A[op.y+i-1][op.x]);
    }
    c += w_align*(op.y == 0 || A[op.y-1][op.x] != A[op.y][op.x]);
    c += w_align*(op.y+op.L == N || A[op.y+op.L][op.x] != A[op.y+op.L-1][op.x]);
  }
  return c;
}

int count_black(vector<string>& A,const op_t op) {
  int c = 0;
  if (op.d == 0) {
    for (int i=0; i<op.L; i++) {
      c += (A[op.y][op.x+i] & 1);
    }
  } else {
    for (int i=0; i<op.L; i++) {
      c += (A[op.y+i][op.x] & 1);
    }
  }
  return c;
}

void show_pattern(vector<string>& A,const op_t op) {
  if (op.d == 0) {
    cerr << "H";
    cerr << ((op.x==0) ? '|' : "_#"[A[op.y][op.x-1] & 1]);
    for (int i=0; i<op.L; i++) {
      cerr << A[op.y][op.x+i];
    }
    cerr << ((op.x+op.L==N) ? '|' : "_#"[A[op.y][op.x+op.L] & 1]);
  } else {
    cerr << "V";
    cerr << ((op.y==0) ? '|' : "_#"[A[op.y-1][op.x] & 1]);
    for (int i=0; i<op.L; i++) {
      cerr << A[op.y+i][op.x];
    }
    cerr << ((op.y+op.L==N) ? '|' : "_#"[A[op.y+op.L][op.x] & 1]);
  }
  cerr << endl;
}

int score(const vector<string>& A) {
  int c = 0;
  for (int y=0; y<N; y++)
    for (int x=0; x<N; x++)
      c += (A[y][x] == '0');

  return c;
}

vector<op_t> solve(vector<string> A, const vector<int>& Ls) {
  vector<op_t> ops(K);

  vector<pair<int,int>> ord;
  for (int i=0; i<K; i++) 
    ord.push_back(make_pair(-Ls[i], i));
  //sort(ord.begin(), ord.end());

  //for (int i=0; i<K; i++) {
  for (const auto& pa : ord) {
    int i = pa.second;
    int L = Ls[i];

    bool verbose = false && (i == 143);
    //cerr << "i:" << i << " " << L << endl;
    
    op_t best_op;
    int best_c = -12345;
    for (int y=0; y<N; y++)
      for (int x=0; x<N; x++)
	for (int d=0; d<2; d++) {
	  op_t op(x, y, L, d);
	  if (!op.is_valid())
	    continue;
	  int c = evaluate(A, op);
	  if (verbose) {
	    cerr << ((c>9) ? "" : " ") << c << " ";
	    show_pattern(A, op);
	  }	    
	  if (c > best_c) {
	    best_c = c;
	    best_op = op;
	  }
	}
    if (verbose) {
      cerr << best_c << endl;
      show_pattern(A, best_op);
      exit(1);
    }
  
    //ops.push_back(best_op);
    ops[i] = best_op;
    apply(A, best_op);
  }

  xor128_t rng(192993);
  for (int lp=0; lp<3; lp++) {
    for (int i=0; i<K; i++) {      
      //for (int ii=0; ii<K; ii++) {
      //int i = rng.get(K);
      if (ops[i].L < 3-lp)
	continue;
      op_t best_op = ops[i];
      apply(A, best_op);
      //int best_c = count_black(A, best_op);
      int best_c = evaluate(A, best_op);
      int L = best_op.L;
      for (int y=0; y<N; y++)
	for (int x=0; x<N; x++)
	  for (int d=0; d<2; d++) {
	    op_t op(x, y, L, d);
	    if (!op.is_valid())
	      continue;
	    //int c = count_black(A, op);
	    int c = evaluate(A, op);
	    if (c > best_c) {
	      best_c = c;
	      best_op = op;
	    }
	  }
  
      ops[i] = best_op;
      apply(A, best_op);
    }
  }
  
  return ops;
}

void run_testcases() {
  N = 60;
  K = 500;
  vector<int> L(K);
  vector<string> A(N, string(N, '0'));
  for (int seed=1000; seed<=1099; seed++) {
    xor128_t rng(seed);
    for (int i=0; i<K; i++)
      L[i] = rng.get(1, 25);
    for (int y=0; y<N; y++)
      for (int x=0; x<N; x++)
	A[y][x] = '0' + rng.get(2);

    int s0 = score(A);
    auto ops = solve(A, L);
    for (const auto& op : ops) 
      apply(A, op);
    int s1 = score(A);
    cout << "seed: " << seed << endl;
    cout << "Score = " << s1 - s0 << endl;
  }
}

int main(int argc,const char *argv[]) {
  
  if (argc > 1) {
    run_testcases();

    return 0;
  }
  
  cin >> N >> K;
  vector<int> L(K);

  for (int i=0; i<K; i++)
    cin >> L[i];

  vector<string> A(N);
  for (int i=0; i<N; i++) {
    cin >> A[i];
    A[i].resize(N);
  }

  int s0 = score(A);
  auto ret = solve(A, L);
  for (const auto& op : ret) 
    apply(A, op);
  int s1 = score(A);
  cerr << "Score = " << s1 - s0 << endl;

  assert(ret.size() == K);
  for (int i=0; i<K; i++) {
    auto v(ret[i].to_v());
    cout << v[0]
	 << " " << v[1]
	 << " " << v[2]
	 << " " << v[3] << endl;
  }
}