結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 machy
|
| 提出日時 | 2018-05-28 09:07:56 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,744 bytes |
| コンパイル時間 | 31,945 ms |
| 実行使用メモリ | 1,628 KB |
| スコア | 7,984 |
| 最終ジャッジ日時 | 2018-05-28 09:08:29 |
|
ジャッジサーバーID （参考情報） |
judge9 / |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 WA * 8 RE * 1 |
ソースコード
#include <iostream>
#include <vector>
#include <cassert>
#include <random>
#include <string>
using namespace std;
#include <sys/time.h>
class Timer{
protected:
double startTime;
double limit;
bool alreadyTimeup;
public:
Timer(double time_limit){
set(time_limit);
}
void set(double time_limit){
limit = time_limit;
startTime = now();
alreadyTimeup = false;
}
bool timeup(){
if(alreadyTimeup) return true;
if(now() - startTime > limit){
alreadyTimeup = true;
return true;
}else{
return false;
}
}
double elapse(){
return now() - startTime;
}
double used(){
return elapse() / limit;
}
protected:
double now(){
timeval tv;
gettimeofday(&tv, 0);
return tv.tv_sec + tv.tv_usec * 1e-6;
}
};
#include<vector>
#include<string>
template <typename T>
struct PointBase{
T y, x;
PointBase(T y_, T x_):y(y_),x(x_){}
PointBase(){}
bool operator<(const PointBase& op) const{
if(this->y == op.y) return this->x < op.x;
return this->y < op.y;
}
bool operator==(const PointBase& op) const{
return this->y == op.y && this->x == op.x;
}
PointBase& operator+=(const PointBase& op){
this->y += op.y; this->x += op.x;
return *this;
}
};
template <typename T> string to_string(const PointBase<T>& p){
return string("(") + to_string(p.y) + "," + to_string(p.x) + ")";
}
template <typename T> std::ostream& operator<<(std::ostream& os, const PointBase<T>& p) {
os << to_string(p);
return os;
}
typedef PointBase<int> Point;
template <typename T>
struct BoardBase{
int h, w;
vector<T> data;
BoardBase(int h_, int w_, const T& init):h(h_),w(w_),data(h * w, init){}
void put(Point& p, const T& val){
data[p.y*w + p.x] = val;
}
void put(int pos, const T& val){
data[pos] = val;
}
void put(int y, int x, const T& val){
data[y*w + x] = val;
}
T& get(Point& p){
return data[p.y*w + p.x];
}
T& get(int pos){
return data[pos];
}
T& get(int y, int x){
return data[y*w + x];
}
};
typedef BoardBase<int> Board;
typedef long long LL;
//*
mt19937 randint(123123123);
/*/
struct XORShift{
uint32_t operator()(){
static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
uint32_t t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
} randint;
//*/
const int N = 60, K = 500;
vector<int> L;
Timer timer(0.9);
int componentCount(uint64_t val, uint64_t val_zero){
uint64_t comp = (val ^ (val<<1)) & val;
uint64_t bridge = val_zero & (val >> 1) & (val << 1);
return __builtin_popcountll(comp) - __builtin_popcountll(bridge);
}
int componentCount(vector<uint64_t>& vec, vector<uint64_t>& vec_zero){
int ans = 0;
for(int i = 0; i < N; ++i){
ans += componentCount(vec[i], vec_zero[i]);
}
return ans;
}
int componentCount(vector<uint64_t>& rows, vector<uint64_t>& cols, vector<uint64_t>& rows_zero, vector<uint64_t>& cols_zero){
return componentCount(rows, rows_zero) + componentCount(cols, cols_zero);
}
int componentCountDiff(vector<uint64_t>& rows, vector<uint64_t>& cols, vector<uint64_t>& rows_zero, vector<uint64_t>& cols_zero, int y, int x){
return componentCount(rows[y], rows_zero[y]) + componentCount(cols[x], cols_zero[x]);
}
struct State{
vector<uint64_t> rows;
vector<uint64_t> cols;
vector<Point> assign;
vector<bool> assign_row;
int score;
int last_cur;
Point last_p;
bool last_is_row;
State(vector<uint64_t>& rows_, vector<uint64_t>& cols_)
:rows(rows_), cols(cols_), assign(K), assign_row(K){
score = 0;
for(int i = 0; i < K; ++i){
assign[i] = Point(0, 0);
assign_row[i] = true;
rows[0] ^= (1ULL << (0+L[i])) - (1ULL << 0);
score += __builtin_popcountll(rows[i]);
score += __builtin_popcountll(cols[i]);
}
}
void place(int cur, int y, int x, int is_row){
// undo info
last_cur = cur;
last_p = assign[cur];
last_is_row = assign_row[cur];
// unplace
Point p = assign[cur];
if(assign_row[cur]){
score -= __builtin_popcountll(rows[p.y]);
rows[p.y] ^= (1ULL << (p.x+L[cur])) - (1ULL << p.x);
score += __builtin_popcountll(rows[p.y]);
}else{
score -= __builtin_popcountll(cols[p.x]);
cols[p.x] ^= (1ULL << (p.y+L[cur])) - (1ULL << p.y);
score += __builtin_popcountll(cols[p.x]);
}
// place
if(is_row){
assign[cur] = Point(y, x);
assign_row[cur] = true;
score -= __builtin_popcountll(rows[y]);
rows[y] ^= (1ULL << (x+L[cur])) - (1ULL << x);
score += __builtin_popcountll(rows[y]);
}else{
assign[cur] = Point(y, x);
assign_row[cur] = false;
score -= __builtin_popcountll(cols[x]);
cols[x] ^= (1ULL << (y+L[cur])) - (1ULL << y);
score += __builtin_popcountll(cols[x]);
}
}
void undo(){
place(last_cur, last_p.y, last_p.x, last_is_row);
}
vector<pair<Point, Point>> getAssign() const{
vector<pair<Point, Point>> res(K);
for(int i = 0; i < K; ++i){
res[i].first = assign[i];
if(assign_row[i]){
res[i].second = Point(assign[i].y + 1, assign[i].x + L[i]);
}else{
res[i].second = Point(assign[i].y + L[i], assign[i].x + 1);
}
}
return res;
}
int getScore() const{ return score; }
};
vector<pair<Point, Point>> optimize(vector<uint64_t>& rows, vector<uint64_t>& cols){
State s(rows, cols);
State best_s = s;
double threshold_base = 5.0;
int threshold = threshold_base;
for(LL e = 0; ; ++e){
if((e & 0xff) == 0xff){
threshold = 5.0 * (1.0 - timer.used());
if(timer.timeup()) break;
}
uint32_t r = randint();
bool is_row = (r & 1);
int cur = (r >> 1) % N;
int offset = randint() % (N+1 - L[cur]);
if(is_row){
int y = randint() % N;
s.place(cur, y, offset, true);
}else{
int x = randint() % N;
s.place(cur, offset, x, true);
}
if(s.getScore()-threshold <= best_s.getScore()){
if(s.getScore() < best_s.getScore()){
cerr << "update : " << best_s.getScore() << " -> " << s.getScore() << endl;
best_s = s;
}
}else{
s.undo();
}
}
return best_s.getAssign();
}
int calcScore(vector<vector<int>>& board1, vector<vector<int>>& board2){
int score = 0;
for(int y = 0; y < N; ++ y){
for(int x = 0; x < N; ++x){
score += board1[y][x] - board2[y][x];
}
}
return score;
}
int main(){
int N_, K_;
cin >> N_ >> K_;
assert(N == N_ && K == K_);
L.resize(K);
for(int i = 0; i < K; ++i){
cin >> L[i];
}
vector<vector<int>> board(N, vector<int>(N));
for(int y = 0; y < N; ++y){
string s;
cin >> s;
for(int x = 0; x < N; ++x){
board[y][x] = (s[x] == '1')? 1: 0;
}
}
vector<uint64_t> rows(N), cols(N);
vector<uint64_t> rows_zero(N), cols_zero(N);
vector<Point> one_index;
for(int y = 0; y < N; ++y){
for(int x = 0; x < N; ++x){
if(board[y][x] == 1){
rows[y] |= (1ULL << x);
one_index.emplace_back(y, x);
}else{
rows_zero[y] |= (1ULL << x);
cols_zero[x] |= (1ULL << y);
}
}
}
cerr << "comp cnt : " << componentCount(rows, cols, rows_zero, cols_zero) << endl;
int comp_best = componentCount(rows, cols, rows_zero, cols_zero);
int comp_score = comp_best;
vector<uint64_t> rows_best = rows, cols_best = cols;
LL max_e = 1000*1000*5;
for(LL e = 0; e < max_e; ++e){
int threshold = 5.0 * (max_e - e) / max_e;
int r = randint() % one_index.size();
int y = one_index[r].y;
int x = one_index[r].x;
int score_prev = componentCountDiff(rows, cols, rows_zero, cols_zero, y, x);
rows[y] ^= (1ULL << x);
cols[x] ^= (1ULL << y);
int score_next = componentCountDiff(rows, cols, rows_zero, cols_zero, y, x);
//cerr << comp_best << ", " << score << ", " << score - comp_best << endl;
if(comp_score + score_next - score_prev - threshold <= comp_best){
comp_score += score_next - score_prev;
//assert(score == componentCount(rows, cols, rows_zero, cols_zero));
if(comp_score < comp_best){
comp_best = comp_score;
cerr << comp_best << endl;
}
}else{
rows[y] ^= (1ULL << x);
cols[x] ^= (1ULL << y);
}
}
vector<pair<Point, Point>> assign = optimize(rows, cols);
vector<vector<int>> ans_board = board;
for(pair<Point, Point> p: assign){
cout << p.first.y+1 << " " << p.first.x+1 << " " << p.second.y << " " << p.second.x << endl;
for(int y = p.first.y; y < p.second.y; ++y){
for(int x = p.first.x; x < p.second.x; ++x){
ans_board[y][x] = 1 - ans_board[y][x];
}
}
}
int score = calcScore(board, ans_board);
cerr << "Score = " << score << endl;
return 0;
}