結果
| 問題 | No.5002 stick xor |
| ユーザー |
 yowa
|
| 提出日時 | 2018-05-29 14:26:44 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,402 bytes |
| コンパイル時間 | 37,387 ms |
| スコア | 0 |
| 最終ジャッジ日時 | 2018-05-29 14:27:23 |
|
ジャッジサーバーID （参考情報） |
judge8 / |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | - |
ソースコード
#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<10; lp++) {
for (int i=0; i<K; i++) {
//for (int ii=0; ii<K; ii++) {
//int i = rng.get(K);
if (ops[i].L < 10-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;
}
}