結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 sumoru
|
| 提出日時 | 2018-05-27 14:49:09 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 957 ms / 1,000 ms |
| コード長 | 12,009 bytes |
| コンパイル時間 | 35,485 ms |
| 実行使用メモリ | 1,644 KB |
| スコア | 44,785 |
| 最終ジャッジ日時 | 2018-05-27 14:49:46 |
|
ジャッジサーバーID （参考情報） |
judge8 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<random>
#include<sys/time.h>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ in >> p.first >> p.second; return in; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }
#define LIMIT 0.95
mt19937 mt;
timeval start;
double elapsed(){
timeval now;
gettimeofday(&now, nullptr);
return (now.tv_sec - start.tv_sec) + (now.tv_usec - start.tv_usec) / 1e6;
}
struct Ans {
char a, b, c, d;
Ans() = default;
Ans(int a, int b, int c, int d): a(a), b(b), c(c), d(d) {}
friend ostream& operator << (ostream& out, Ans& e) {
return out << e.a + 1 << ' ' << e.b + 1 << ' ' << e.c + 1 << ' ' << e.d + 1;
}
bool operator == (const Ans& e) const {
// return *(int*)(this) == *(int*)(&e);
return a == e.a && b == e.b && c == e.c && d == e.d;
}
bool operator < (const Ans&) const { return false; }
};
int main(){
mt = mt19937(random_device()());
gettimeofday(&start, nullptr);
cin.tie(0);
ios::sync_with_stdio(false);
int n, k;
cin >> n >> k;
vector<int> ls(k); cin >> ls;
vector<string> as(n); cin >> as;
for(auto& a : as){ for(auto& e : a){ e -= '0'; } }
auto as0 = as;
auto calc = [&](){
int num = 0;
for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){
num += as[i][j];
} }
return num;
};
int score0 = calc();
vector<Ans> ans(k);
auto rev = [&](int y, int x){
as[y][x] = !as[y][x];
};
auto put = [&](Ans a){
int ret = 0;
for(int y = a.a; y <= a.c; y++){
for(int x = a.b; x <= a.d; x++){
rev(y, x);
ret += as[y][x] * 2 - 1;
}
}
return ret;
};
auto findBestFast = [&](int l){
pair<int, Ans> ret(-1, {});
for(int y = 0; y < n; y++){
pair<int, Ans> cand(0, Ans{y, 0, y, l - 1});
for(int j = 0; j < l; j++){
cand.first += as[y][j];
}
cand.first -= (as[y][0] && y && as[y - 1][0] && y + 1 < n && as[y + 1][0]);// + as[y][l];
ret = max(ret, cand);
for(int x = 1; x < n - l + 1; x++){
cand.first -= as[y][x - 1];
cand.first += as[y][x + l - 1];
cand.first += (as[y][x - 1] && (y && as[y - 1][x - 1] && y + 1 < n && as[y + 1][x - 1]));// + as[y][l + x - 1];
cand.first -= (as[y][x] && (y && as[y - 1][x] && y + 1 < n && as[y + 1][x]));// + (l + x < n && as[y][l + x]);
cand.second.b++;
cand.second.d++;
ret = max(ret, cand);
}
}
for(int x = 0; x < n; x++){
pair<int, Ans> cand(0, Ans{0, x, l - 1, x});
for(int j = 0; j < l; j++){
cand.first += as[j][x];
}
cand.first -= (as[0][x] && x && as[0][x - 1] && x + 1 < n && as[0][x + 1]);// + as[l][x];
for(int y = 1; y < n - l + 1; y++){
cand.first -= as[y - 1][x];
cand.first += as[y + l - 1][x];
cand.first += (as[y - 1][x] && x && as[y - 1][x - 1] && x + 1 < n && as[y - 1][x + 1]);// + as[l + y - 1][x];
cand.first -= (as[y][x] && x && as[y][x - 1] && x + 1 < n && as[y][x + 1]);// + (l + y < n && as[l + y][x]);
cand.second.a++;
cand.second.c++;
ret = max(ret, cand);
}
}
return ret;
};
auto findBest = [&](int l){
pair<int, Ans> ret(-1, {});
for(int y = 0; y < n; y++){
for(int x = 0; x < n - l; x++){
pair<int, Ans> cand(0, Ans{y, x, y, x + l - 1});
for(int j = 0; j < l; j++){
cand.first += as[y][x + j] * 2;
cand.first += l > 2 && !as[y][x + j] && y && as[y - 1][x + j] && y + 1 < n && as[y + 1][x + j];
}
ret = max(ret, cand);
}
}
for(int y = 0; y < n - l; y++){
for(int x = 0; x < n; x++){
pair<int, Ans> cand(0, Ans{y, x, y + l - 1, x});
for(int j = 0; j < l; j++){
cand.first += as[y + j][x] * 2;
cand.first += l > 2 && !as[y + j][x] && x && as[y + j][x - 1] && x + 1 < n && as[y + j][x + 1];
}
ret = max(ret, cand);
}
}
return ret;
};
auto findGood = [&](int l){
pair<int, Ans> ra(-1, {}), rb(-1, {});
for(int y = 0; y < n; y++){
pair<int, Ans> cand(0, Ans{y, 0, y, l - 1});
for(int j = 0; j < l; j++){
cand.first += as[y][j];
}
ra = cand;
for(int x = 1; x < n - l + 1; x++){
cand.first -= as[y][x - 1];
cand.first += as[y][x + l - 1];
cand.second.b++;
cand.second.d++;
if(rb < cand){
rb = cand;
if(ra < rb){
swap(ra, rb);
}
}
}
}
for(int x = 0; x < n; x++){
pair<int, Ans> cand(0, Ans{0, x, l - 1, x});
for(int j = 0; j < l; j++){
cand.first += as[j][x];
}
if(rb < cand){
rb = cand;
if(ra < rb){
swap(ra, rb);
}
}
for(int y = 1; y < n - l + 1; y++){
cand.first -= as[y - 1][x];
cand.first += as[y + l - 1][x];
cand.second.a++;
cand.second.c++;
if(rb < cand){
rb = cand;
if(ra < rb){
swap(ra, rb);
}
}
}
}
return mt() & 1 ? ra : rb;
};
int maxi = 0;
auto as1 = as;
auto ans1 = ans;
vector<int> is, is2, is3;
int thre = 7, thre2 = 2;
for(int i = 0; i < k; i++){
(ls[i] > thre ? is : ls[i] > thre2 ? is2 : is3).push_back(i);
}
for(int _ = 0; _ < 10; _++){
// int c2 = 0;
as = as0;
for(auto i : is){
auto p = findBestFast(ls[i]);
// auto p = findBest(ls[i]);
// c2 += p.first * 2 - ls[i] < -6;
// if(p.first * 2 - ls[i] < 1 && (ls[i] == 25 || ls[i] == 23)){
// p.second = {0, 0, 0, ls[i] - 1};
// c2++;
// }
// if(p.first * 2 - ls[i] < -6){
// p.second = {0, 0, 0, ls[i] - 1};
// // printde(ls[i]);
// }
put(ans[i] = p.second);
}
int cand = score0 - calc();
if(maxi < cand){
maxi = cand;
ans1 = ans;
as1 = as;
}
printde(cand);
shuffle(is.begin(), is.end(), mt);
// printde(c2);
}
as = as1;
ans = ans1;
int cnt = 0;
double d;
while((d = elapsed()) < LIMIT * 0.6){ for(int _ = 0; _ < 100; _++){
cnt++;
int i = is[mt() % is.size()];
auto& a = ans[i];
int diff = put(a);
// auto a2 = findBestFast(ls[i]).second;
auto a2 = findGood(ls[i]).second;
// a = findBest(ls[i]).second;
diff += put(a2);
// static const double startT = 10, endT = 0.01;
// double temp = startT + (endT - startT) * min(1.0, elapsed() / LIMIT);
// if(exp(diff / temp) * (1ull << 32) > mt()){
// if(diff > 1){
if(diff > (d < LIMIT * 0.4)){
put(a2);
put(a);
continue;
}else{
a = a2;
}
if(a.a == a.c){
if(a.d + 1 < n && as[a.a][a.b] && (as[a.a][a.d + 1] || (a.a && as[a.a - 1][a.d] && a.a + 1 < n && as[a.a + 1][a.d]))){
// if(a.d + 1 < n && as[a.a][a.b] && as[a.a][a.d + 1]){
rev(a.a, a.b);
rev(a.a, a.d + 1);
a.b++; a.d++;
}else if(a.b && as[a.a][a.b - 1] && as[a.a][a.d]){
rev(a.a, a.b - 1);
rev(a.a, a.d);
a.b--; a.d--;
}
}
if(a.b == a.d){
if(a.c + 1 < n && as[a.a][a.b] && as[a.c + 1][a.b]){
rev(a.a, a.b);
rev(a.c + 1, a.b);
a.a++; a.c++;
}else if(a.a && as[a.a - 1][a.b] && as[a.c][a.b]){
rev(a.a - 1, a.b);
rev(a.c, a.b);
a.a--; a.c--;
}
}
} }
printde(cnt);
int score = score0 - calc();
printde(score);
as0 = as;
maxi = 0;
for(int _ = 0; _ < 10; _++){
as = as0;
for(auto i : is2){
// put(ans[i] = findBestFast(ls[i]).second);
put(ans[i] = findBest(ls[i]).second);
}
int cand = score0 - calc();
if(maxi < cand){
maxi = cand;
ans1 = ans;
as1 = as;
}
printde(cand);
shuffle(is2.begin(), is2.end(), mt);
}
as = as1;
ans = ans1;
while((d = elapsed()) < LIMIT){ for(int _ = 0; _ < 100; _++){
int i = mt() % k;
if(ans[i] == Ans()){ continue; }
auto& a = ans[i];
put(a);
a = findBestFast(ls[i]).second;
// a = findBest(ls[i]).second;
put(a);
// int diff = put(a);
// auto a2 = findGood(ls[i]).second;
// // a = findBest(ls[i]).second;
// diff += put(a2);
// if(diff > (d < LIMIT * 0.85)){
// put(a2);
// put(a);
// continue;
// }else{
// a = a2;
// }
if(a.a == a.c){
if(a.d + 1 < n && (as[a.a][a.b] + as[a.a][a.d + 1] > int(mt() & 1))){
rev(a.a, a.b);
rev(a.a, a.d + 1);
a.b++; a.d++;
}else if(a.b && (as[a.a][a.b - 1] + as[a.a][a.d]) > int(mt() & 1)){
rev(a.a, a.b - 1);
rev(a.a, a.d);
a.b--; a.d--;
}
}
if(a.b == a.d){
if(a.c + 1 < n && (as[a.a][a.b] + as[a.c + 1][a.b]) > int(mt() & 1)){
rev(a.a, a.b);
rev(a.c + 1, a.b);
a.a++; a.c++;
}else if(a.a && (as[a.a - 1][a.b] + as[a.c][a.b]) > int(mt() & 1)){
rev(a.a - 1, a.b);
rev(a.c, a.b);
a.a--; a.c--;
}
}
} }
score = score0 - calc();
printde(score);
vector<pair<int, int>> ps;
for(auto i : is3){
ps.emplace_back(ls[i], i);
}
sort(ps.rbegin(), ps.rend());
int c3 = 0;
for(auto& p : ps){
int i = p.second;
c3 += ls[i];
put(ans[i] = findBestFast(ls[i]).second);
}
// for(int i = 0; i < k; i++){
// if(ls[i] != 15){ continue; }
// auto a = ans[i];
// int cnt = 0;
// for(int y = a.a; y <= a.c; y++){
// for(int x = a.b; x <= a.d; x++){
// cnt += as[y][x];
// }
// }
// printde(cnt);
// }
score = score0 - calc();
printde(score, c3);
for(auto& e : ans){
cout << e << '\n';
}
}