結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 mai
|
| 提出日時 | 2018-05-31 00:01:21 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 964 ms / 1,000 ms |
| コード長 | 20,608 bytes |
| コンパイル時間 | 37,046 ms |
| 実行使用メモリ | 1,620 KB |
| スコア | -43,899 |
| 最終ジャッジ日時 | 2018-05-31 00:02:00 |
|
ジャッジサーバーID （参考情報） |
judge7 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
#define debug(v) {printf("L%d %s > ",__LINE__,#v);cout<<(v)<<endl;}
#define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:(v)){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) {printf("L%d %s > ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;}
#define debugaa(m,h,w) {printf("L%d %s >\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}}
#define ALL(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(remove_const<decltype(l)>::type cnt=0;(cnt)<(l);++(cnt))
#define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define diterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);--(cnt))
const ll MD = 1000000007ll; const long double PI = 3.1415926535897932384626433832795L;
inline void assert_call(bool assertion, function<void()> f) { if (!assertion) { cerr << "assertion fault:" << endl; f(); abort(); } }
template<typename T1, typename T2> inline ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << '(' << p.first << ':' << p.second << ')'; return o; }
template<typename Vec> inline ostream& _ostream_vecprint(ostream &o, const Vec& p) { o << '['; for (auto& e : p) o << e << ','; o << ']'; return o; }
template<typename T> inline ostream& operator<<(ostream& o, const vector<T>& v) { return _ostream_vecprint(o, v); }
template<typename T, size_t S> inline ostream& operator<<(ostream& o, const array<T, S>& v) { return _ostream_vecprint(o, v); }
template<typename T> inline T& maxset(T& to, const T& val) { return to = max(to, val); }
template<typename T> inline T& minset(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(code); }
struct XorShift {
using result_type = uint64_t;
result_type x_;
XorShift(result_type x = 88172645463325252ull) :x_(x) {};
static constexpr inline result_type min() { return 0ull; }
static constexpr inline result_type max() { return numeric_limits<result_type>::max(); }
inline result_type operator()() { x_ ^= x_ << 7; return x_ ^= x_ >> 9; }
inline void discard(unsigned long long z) { while (z--) operator()(); }
};
XorShift randdev;
template<typename T> inline T rand(T l, T h) { return uniform_int_distribution<T>(l, h)(randdev); }
template<> inline double rand<double>(double l, double h) { return uniform_real_distribution<double>(l, h)(randdev); }
template<> inline float rand<float>(float l, float h) { return uniform_real_distribution<float>(l, h)(randdev); }
#if defined(_WIN32) || defined(_WIN64)
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#elif defined(__GNUC__)
#else
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
namespace {
#define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E)
class MaiScanner {
public:
template<typename T> void input_integer(T& var) {
var = 0; T sign = 1;
int cc = getchar_unlocked();
for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
if (cc == '-') sign = -1;
for (; '0' <= cc && cc <= '9'; cc = getchar_unlocked())
var = (var << 3) + (var << 1) + cc - '0';
var = var * sign;
}
inline int c() { return getchar_unlocked(); }
inline MaiScanner& operator>>(int& var) { input_integer<int>(var); return *this; }
inline MaiScanner& operator>>(long long& var) { input_integer<long long>(var); return *this; }
inline MaiScanner& operator>>(string& var) {
int cc = getchar_unlocked();
for (; !isvisiblechar(cc); cc = getchar_unlocked());
for (; isvisiblechar(cc); cc = getchar_unlocked())
var.push_back(cc);
return *this;
}
template<typename IT> void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; }
};
class MaiPrinter {
public:
template<typename T>
void output_integer(T var) {
if (var == 0) { putchar_unlocked('0'); return; }
if (var < 0)
putchar_unlocked('-'),
var = -var;
char stack[32]; int stack_p = 0;
while (var)
stack[stack_p++] = '0' + (var % 10),
var /= 10;
while (stack_p)
putchar_unlocked(stack[--stack_p]);
}
inline MaiPrinter& operator<<(char c) { putchar_unlocked(c); return *this; }
inline MaiPrinter& operator<<(int var) { output_integer<int>(var); return *this; }
inline MaiPrinter& operator<<(long long var) { output_integer<long long>(var); return *this; }
inline MaiPrinter& operator<<(char* str_p) { while (*str_p) putchar_unlocked(*(str_p++)); return *this; }
inline MaiPrinter& operator<<(const string& str) {
const char* p = str.c_str();
const char* l = p + str.size();
while (p < l) putchar_unlocked(*p++);
return *this;
}
template<typename IT> void join(IT begin, IT end, char sep = '\n') { for (auto it = begin; it != end; ++it) *this << *it << sep; }
};
}
MaiScanner scanner;
MaiPrinter printer;
#define TIME chrono::system_clock::now()
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())
// Edge構造体を定義する無向グラフ
class GraphE {
public:
typedef int W_T;
struct Edge {
int u, v;
W_T value;
Edge(int from = 0, int to = 0, W_T value = 0) :u(from), v(to), value(value) {}
inline int to(int _v) const { return _v == v ? u : v; }
};
size_t n;
vector<vector<int>> vertex_to;
vector<Edge> edges;
GraphE(int n = 1) :n(n), vertex_to(n) { }
void resize(size_t _n) {
n = _n;
vertex_to.resize(_n);
}
void connect(int from, int to, W_T val = 0) {
vertex_to[(size_t)from].push_back((int)edges.size());
vertex_to[(size_t)to].push_back((int)edges.size());
edges.emplace_back(from, to, val);
}
};
// Rectangle
struct Rect {
int top, left, bottom, right;
Rect(int t = 0, int l = 0, int b = 0, int r = 0) :top(t), left(l), bottom(b), right(r) { }
inline int area() { return (right - left + 1)*(bottom - top + 1); }
inline bool operator==(Rect r) const { return top == r.top&&left == r.left&&bottom == r.bottom&&right == r.right; }
inline bool operator<(Rect r) const { return make_tuple(top, left, bottom, right) < make_tuple(r.top, r.left, r.bottom, r.right); }
};
/// <summary>
/// i番目の要素を削除する．削除後の順序は保証されない
/// </summary>
template<typename T>
void vec_erase(vector<T>& vec, size_t idx) {
if (vec.size() != idx + 1)
swap(vec[idx], vec.back());
vec.pop_back();
}
auto beginTime = TIME;
// 問題文と入力
const int N = 60, K = 500;
int L[K];
int A[N][N];
const int Lmax = 25;
// 長さiの長方形のインデックス
// L[j]=iであるようなjの集合が格納される．
vector<int> idxsL[Lmax + 1];
//
vector<vector<Rect>> result(Lmax + 1);
// workspace
decltype(A) my_A;
inline void apply(decltype(A) f, Rect r) {
iterate(y, r.top, r.bottom + 1)
iterate(x, r.left, r.right + 1)
f[y][x] ^= 1;
}
//
void input() {
int n, k;
scanner >> n >> k;
assert(n == N && k == K);
scanner.in(L, L + K);
repeat(i, N) {
string str; scanner >> str;
repeat(j, N) A[i][j] = str[j] == '0'; // << ============== スコア最小を目指す
}
// - - - - -
repeat(i, K)
idxsL[L[i]].push_back(i);
}
//
void solve1() {
//copy(A[0], A[N], my_A[0]);
repeat(i, N) repeat(j, N) my_A[i][j] = A[i][j];
// l in 2..Lmax
diterate(l, Lmax, 1) {
repeat(_, idxsL[l].size()) {
pair<int, int> best_score(-1, 0);
Rect best_rect;
decltype(randdev()) best_seed;
// 水平方向に置く場合を全探索
// 探索
repeat(y, N) {
int sum = 0;
repeat(x, l - 1)
sum += my_A[y][x];
repeat(x, N + 1 - l) {
sum += my_A[y][x + l - 1];
int score = sum + (my_A[y][x] * my_A[y][x + l - 1]) * 5;
auto p = make_pair(score, (int)randdev());
if (best_score < p)
best_score = p,
best_rect = Rect(y, x, y, x + l - 1);
sum -= my_A[y][x];
}
}
// 垂直方向に置く場合を全探索
// 探索
repeat(x, N) {
int sum = 0;
repeat(y, l - 1)
sum += my_A[y][x];
repeat(y, N + 1 - l) {
sum += my_A[y + l - 1][x];
int score = sum + (my_A[y][x] * my_A[y + l - 1][x]) * 5;
auto p = make_pair(score, (int)randdev());
if (best_score < p)
best_score = p,
best_rect = Rect(y, x, y + l - 1, x),
best_seed = randdev();
sum -= my_A[y][x];
}
}
result[l].push_back(best_rect);
apply(my_A, best_rect);
}
}
}
//
void solve2() {
// 調整
diterate(l, Lmax, 1) {
for (Rect& rect : result[l]) {
if (rect.left == rect.right) {
int x = rect.left;
if (0 < rect.top && my_A[rect.top - 1][x] == 1 && my_A[rect.bottom][x] == 1)
my_A[rect.top - 1][x] ^= 1, my_A[rect.bottom][x] ^= 1,
--rect.top, --rect.bottom;
else if (rect.bottom < N - 1 && my_A[rect.top][x] == 1 && my_A[rect.bottom + 1][x] == 1)
my_A[rect.top][x] ^= 1, my_A[rect.bottom + 1][x] ^= 1,
++rect.top, ++rect.bottom;
}
else if (rect.top == rect.bottom) {
int y = rect.top;
if (0 < rect.left && my_A[y][rect.left - 1] == 1 && my_A[y][rect.right] == 1)
my_A[y][rect.left - 1] ^= 1, my_A[y][rect.right] ^= 1,
--rect.left, --rect.right;
else if (rect.right < N - 1 && my_A[y][rect.left] == 1 && my_A[y][rect.right + 1] == 1)
my_A[y][rect.left] ^= 1, my_A[y][rect.right + 1] ^= 1,
++rect.left, ++rect.right;
}
}
}
}
decltype(A) stored_A;
vector<vector<Rect>> my_result(Lmax + 1);
//
void burning_stage() {
//copy(my_A[0], my_A[N], stored_A[0]);
repeat(i, N) repeat(j, N) stored_A[i][j] = my_A[i][j];
my_result = result;
int best_score = 0;
repeat(i, N) repeat(j, N) best_score += my_A[i][j];
clog << "before : " << best_score << '\n';
int current_score = best_score;
int best_loop = 0;
int current_loop = 0;
int ana_updatecnt = 0;
for (;MILLISEC(TIME - beginTime) < 960; ++current_loop)
{
// thr/1024
int thr = 334;//400 - (current_loop - best_loop) * 2;
int seed = randdev() & 1023;
if (seed & 1) {
int l = rand(2, Lmax);
assert(!my_result[l].empty());
int i = rand(0, (int)my_result[l].size() - 1);
Rect& ri = my_result[l][i];
if (ri.left == ri.right) {
int a0 = ri.top == 0 ? 0 : my_A[ri.top-1][ri.left];
int a1 = my_A[ri.top][ri.left];
int a2 = my_A[ri.bottom][ri.left];
int a3 = ri.bottom == N - 1 ? 0 : my_A[ri.bottom + 1][ri.left];
a0 = a0 * 2 - 1;
a1 = a1 * 2 - 1;
a2 = a2 * 2 - 1;
a3 = a3 * 2 - 1;
if (thr > seed) {
// perhaps unhappy
if (ri.top == 0 || (ri.bottom != N - 1 && randdev() & 1)) {
current_score -= a3 + a1;
my_A[ri.top][ri.left] ^= 1;
my_A[ri.bottom + 1][ri.left] ^= 1;
ri.top++; ri.bottom++;
}
else {
current_score -= a0 + a2;
my_A[ri.bottom][ri.left] ^= 1;
my_A[ri.top - 1][ri.left] ^= 1;
ri.top--; ri.bottom--;
}
}
else {
bool select_up = 0, select_down = 0;
select_up = (ri.top != 0 && a3 + a1 > 0);
select_down = (ri.bottom != N-1 && a0 + a2 > 0);
if (select_up && (!select_down || (randdev()&1))) {
current_score -= a3 + a1;
my_A[ri.top][ri.left] ^= 1;
my_A[ri.bottom + 1][ri.left] ^= 1;
ri.top++; ri.bottom++;
}
else if (select_down) {
current_score -= a0 + a2;
my_A[ri.bottom][ri.left] ^= 1;
my_A[ri.top - 1][ri.left] ^= 1;
ri.top--; ri.bottom--;
}
}
}
else {
int a0 = ri.left == 0 ? 0 : my_A[ri.top][ri.left - 1];
int a1 = my_A[ri.top][ri.left];
int a2 = my_A[ri.top][ri.right];
int a3 = ri.right == N - 1 ? 0 : my_A[ri.top][ri.right + 1];
a0 = a0 * 2 - 1;
a1 = a1 * 2 - 1;
a2 = a2 * 2 - 1;
a3 = a3 * 2 - 1;
if (thr > seed) {
// perhaps unhappy
if (ri.left == 0 || (ri.right != N - 1 && randdev() & 1)) {
current_score -= a3 + a1;
my_A[ri.top][ri.left] ^= 1;
my_A[ri.top][ri.right + 1] ^= 1;
ri.left++; ri.right++;
}
else {
current_score -= a0 + a2;
my_A[ri.top][ri.right] ^= 1;
my_A[ri.top][ri.left - 1] ^= 1;
ri.left--; ri.right--;
}
}
else {
bool select_up = 0, select_down = 0;
select_up = (ri.left != 0 && a3 - a1 > 0);
select_down = (ri.right != N - 1 && a0 - a2 > 0);
if (select_up && (!select_down || (randdev() & 1))) {
current_score -= a3 + a1;
my_A[ri.top][ri.left] ^= 1;
my_A[ri.top][ri.right + 1] ^= 1;
ri.left++; ri.right++;
}
else if (select_down) {
current_score -= a0 + a2;
my_A[ri.top][ri.right] ^= 1;
my_A[ri.top][ri.left - 1] ^= 1;
ri.left--; ri.right--;
}
}
}
}
else {
int l = rand(3, Lmax);
assert(!my_result[l].empty());
assert(!my_result[l - 1].empty());
int i = rand(0, (int)my_result[l].size() - 1); // ながいほう
int j = rand(0, (int)my_result[l - 1].size() - 1); // みじかいほう
Rect ri = my_result[l][i];
Rect rj = my_result[l - 1][j];
int ai, aj = 0;
if (ri.left == ri.right)
ai = my_A[ri.top][ri.left] | my_A[ri.bottom][ri.left];
else
ai = my_A[ri.top][ri.left] | my_A[ri.top][ri.right];
if (rj.left == rj.right) {
if (rj.top != 0) aj |= my_A[rj.top - 1][rj.left];
if (rj.bottom != N-1) aj |= my_A[rj.bottom + 1][rj.left];
}
else {
if (rj.left != 0) aj |= my_A[rj.top][rj.left - 1];
if (rj.right != N - 1) aj |= my_A[rj.top][rj.right + 1];
}
// if (thr > seed) {
// // perhaps unhappy
// }
// else
if (ai && aj) {
vec_erase(my_result[l], i);
vec_erase(my_result[l-1], j);
// ながいほうだった場所にみじかいほうを置く
if (ri.left == ri.right) {
if (my_A[ri.top][ri.left])
my_result[l - 1].emplace_back(ri.top + 1, ri.left, ri.bottom, ri.right),
my_A[ri.top][ri.left] ^= 1;
else if (my_A[ri.bottom][ri.left])
my_result[l - 1].emplace_back(ri.top, ri.left, ri.bottom - 1, ri.right),
my_A[ri.bottom][ri.left] ^= 1;
}
else {
if (my_A[ri.top][ri.left])
my_result[l - 1].emplace_back(ri.top, ri.left + 1, ri.bottom, ri.right),
my_A[ri.top][ri.left] ^= 1;
else if (my_A[ri.top][ri.right])
my_result[l - 1].emplace_back(ri.top, ri.left, ri.bottom, ri.right - 1),
my_A[ri.top][ri.right] ^= 1;
}
// みじかいほうだった場所にながいほうを置く
if (rj.left == rj.right) {
if (rj.top != 0 && (my_A[rj.top - 1][rj.left]))
my_result[l].emplace_back(rj.top - 1, rj.left, rj.bottom, rj.right),
my_A[rj.top - 1][rj.left] ^= 1;
else if (rj.bottom != N - 1 && my_A[rj.bottom + 1][rj.left])
my_result[l].emplace_back(rj.top, rj.left, rj.bottom + 1, rj.right),
my_A[rj.bottom + 1][rj.left] ^= 1;
}
else {
if (rj.left != 0 && (my_A[rj.top][rj.left - 1]))
my_result[l].emplace_back(rj.top, rj.left - 1, rj.bottom, rj.right),
my_A[rj.top][rj.left - 1] ^= 1;
else if (rj.right != N - 1 && my_A[rj.top][rj.right + 1])
my_result[l].emplace_back(rj.top, rj.left, rj.bottom, rj.right + 1),
my_A[rj.top][rj.right + 1] ^= 1;
}
current_score -= 2;
}
}
if (best_score > current_score) {
++ana_updatecnt;
best_score = current_score;
best_loop = current_loop;
// save
//copy(my_A[0], my_A[N], stored_A[0]);
repeat(i, N) repeat(j, N) stored_A[i][j] = my_A[i][j];
result = my_result;
}
if (current_loop - best_loop > 200) {
best_loop = current_loop;
// restore
repeat(i, N) repeat(j, N) my_A[i][j] = stored_A[i][j];
my_result = result;
current_score = best_score;
}
}
clog << "after : " << best_score << '\n';
clog << "ana_updatecnt = " << ana_updatecnt << '\n';
clog << "current_loop = " << current_loop << '\n';
clog << "best_loop = " << best_loop << '\n';
//copy(stored_A[0], stored_A[N], my_A[0]);
repeat(i, N) repeat(j, N) my_A[i][j] = stored_A[i][j];
}
//
void solve_final() {
// l in 1
{
const int l = 1;
{
int cnt = idxsL[1].size();
Rect best_rect;
// 探索
repeat(y, N) repeat(x, N) {
int score = 0;
if (my_A[y][x]) {
result[1].push_back(Rect(y, x, y, x));
// apply(my_A, best_rect);
if (--cnt <= 0) {
y = N, x = N; break;
}
}
}
}
}
}
//
void output() {
vector<Rect> answer(K);
iterate(l, 1, Lmax + 1) repeat(i, idxsL[l].size()) {
answer[idxsL[l][i]] = result[l][i];
}
for (Rect r : answer)
printf("%d %d %d %d\n", r.top + 1, r.left + 1, r.bottom + 1, r.right + 1);
}
int main() {
input();
//beginTime = TIME; // for handinput
solve1();
//solve2();
burning_stage();
solve_final();
output();
return 0;
}