結果

問題 No.5002 stick xor
ユーザー yowayowa
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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