結果
| 問題 | No.5002 stick xor |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2018-06-01 14:05:54 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 984 ms / 1,000 ms |
| コード長 | 23,841 bytes |
| コンパイル時間 | 35,554 ms |
| 実行使用メモリ | 1,768 KB |
| スコア | -49,503 |
| 最終ジャッジ日時 | 2018-06-01 14:06:32 |
|
ジャッジサーバーID （参考情報） |
judge8 / |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 978 ms
1,768 KB |
| testcase_01 | AC | 981 ms
1,768 KB |
| testcase_02 | AC | 978 ms
1,764 KB |
| testcase_03 | AC | 979 ms
1,768 KB |
| testcase_04 | AC | 979 ms
1,768 KB |
| testcase_05 | AC | 979 ms
1,764 KB |
| testcase_06 | AC | 978 ms
1,764 KB |
| testcase_07 | AC | 979 ms
1,764 KB |
| testcase_08 | AC | 982 ms
1,768 KB |
| testcase_09 | AC | 978 ms
1,764 KB |
| testcase_10 | AC | 979 ms
1,764 KB |
| testcase_11 | AC | 984 ms
1,768 KB |
| testcase_12 | AC | 979 ms
1,764 KB |
| testcase_13 | AC | 979 ms
1,764 KB |
| testcase_14 | AC | 978 ms
1,764 KB |
| testcase_15 | AC | 980 ms
1,764 KB |
| testcase_16 | AC | 979 ms
1,768 KB |
| testcase_17 | AC | 979 ms
1,768 KB |
| testcase_18 | AC | 981 ms
1,764 KB |
| testcase_19 | AC | 980 ms
1,768 KB |
| testcase_20 | AC | 980 ms
1,768 KB |
| testcase_21 | AC | 980 ms
1,764 KB |
| testcase_22 | AC | 979 ms
1,764 KB |
| testcase_23 | AC | 977 ms
1,768 KB |
| testcase_24 | AC | 979 ms
1,768 KB |
| testcase_25 | AC | 981 ms
1,764 KB |
| testcase_26 | AC | 978 ms
1,764 KB |
| testcase_27 | AC | 979 ms
1,768 KB |
| testcase_28 | AC | 978 ms
1,768 KB |
| testcase_29 | AC | 979 ms
1,768 KB |
| testcase_30 | AC | 977 ms
1,768 KB |
| testcase_31 | AC | 980 ms
1,764 KB |
ソースコード
#define NDEBUG
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
using namespace std;
namespace {
using Integer = long long; //__int128;
template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
template<class T> istream& operator , (istream& is, T& val){ return is >> val;}
template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
template<class T> ostream& operator , (ostream& os, const T& val){ return os << " " << val;}
template<class H> void print(const H& head){ cout << head; }
template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }
template<class H> void eprint(const H& head){ cerr << head; }
template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }
class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator end(){ return range_iterator( end_, step_); } };
inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }
inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed
mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());
template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }
inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}
constexpr long long mod = 9_ten + 7;
// #ifdef LOCAL_TEST
namespace my_time{
chrono::steady_clock::time_point start_time;
unsigned long long begin_time;
unsigned long long int getCycle()
{
unsigned int low, high;
__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}
void init(){
start_time = chrono::steady_clock::now();
begin_time = getCycle();
}
double sec_per_cycle(){
auto end_time = chrono::steady_clock::now();
double elapsed = chrono::duration_cast<chrono::nanoseconds>(end_time - start_time).count() * 1e-9;
return elapsed / (getCycle() - begin_time);
}
double getTime()
{
static double spc = sec_per_cycle();
return (double)(getCycle() - begin_time) * spc;
}
};
class XorShift{
public:
uint32_t x;
uint32_t y;
uint32_t z;
uint32_t w;
XorShift(){
x = 123456789;
y = 362436069;
z = 521288629;
w = 88675123;
}
XorShift(uint32_t seed){
x = 123456789;
y = 362436069;
z = 521288629;
w = seed;
for(int i=0; i<100; i++){
(*this)();
}
}
uint32_t next() {
uint32_t t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
uint32_t operator () () {
return next();
}
// [0, range)
int operator () (int range){
return (((long long)next()) * range) >> 32 ;
}
// [0, 1.0]
double prob(){
return (next()&0xfffffff) * 3.7252903123397e-9; // 0xfffffff = 268,435,455 = 2^28-1
}
int pp(){
return next()&0x7FFFFFFF;
}
template<class T>
T& operator()(vector<T>& v){
return v[ next()%v.size() ];
}
};
namespace HyperParams{
double eval_a_1 = 0.49852082187348873;
double eval_a_2 = -0.35482954252382465;
double eval_a_t = 1.548388111321954;
double eval_b_1 = -0.7366255153071408;
double eval_b_2 = 0.21777450535335335;
double eval_b_t = -4.96465221443001;
double eval_b_tk = 1.4569216808676524;
double eval_c_1 = 0.028951822167146618;
double eval_c_2 = -0.5464498270514465;
double sort_len_1 = 0.010985776390509258;
double sort_len_2 = 0.000016078283432444965;
}
string generator(int seed){
int n = 60;
int k = 500;
vector<int> L(k);
XorShift rng(seed);
for(auto& l : L) l = rng(25) + 1;
vector<string> A(n, string(n, '0'));
for(int i : range(n)) for(int j : range(n)){
A[i][j] = rng(2) + '0';
}
stringstream ss;
ss << n << " " << k << "\n";
ss << L << "\n";
ss << join(A, "\n") << "\n";
return ss.str();
}
namespace Solver{
XorShift rng(114514);
int n,k;
struct F{
int n;
vector<long long> H;
struct P{
long long one = 0;
long long seg = 0;
long long seg2 = 0;
};
P state;
bool initialized = false;
void flip_cell(long long& h, P& next_state, int col) {
assert( initialized );
bool l = col>0 && ((h>>(col-1))&1);
bool r = ((h>>(col+1))&1);
if( (h>>col)&1 ){
next_state.one--;
if( !l && !r ){
next_state.seg -= 2;
}else if( l && r ){
next_state.seg += 2;
bool ll = col-2>=0 && ((h>>(col-2))&1);
bool rr = (h>>(col+2))&1;
if( ll && rr ){
next_state.seg2 += 2;
}else if( !ll & !rr ){
next_state.seg2 -= 2;
}
}else if( l && !r ){
bool ll = col-2>=0 && ((h>>(col-2))&1);
if( !ll ){
next_state.seg2 -= 2;
}
}else if( !l && r ){
bool rr = (h>>(col+2))&1;
if( !rr ){
next_state.seg2 -= 2;
}
}
}else{
next_state.one++;
if( !l && !r ){
next_state.seg += 2;
}else if( l && r ){
next_state.seg -= 2;
bool ll = col-2>=0 && ((h>>(col-2))&1);
bool rr = (h>>(col+2))&1;
if(ll && rr){
next_state.seg2 -= 2;
}else if(!ll && !rr){
next_state.seg2 += 2;
}
}else if( l && !r ){
bool ll = col-2>=0 && ((h>>(col-2))&1);
if( !ll ){
next_state.seg2 += 2;
}
}else if( !l && r ){
bool rr = (h>>(col+2))&1;
if( !rr ){
next_state.seg2 += 2;
}
}
}
// unsigned int z = (h << 3) >> col;
// z = (z&(z<<1));
// next_state.seg2 -= __builtin_popcount(z ^ (z<<1));
h ^= 1ll<<col;
// z = (h << 3) >> col;
// z = (z&(z<<1));
// next_state.seg2 += __builtin_popcount(z ^ (z<<1));
}
void flip_cell_dbg(long long& h, P& next_state, int col){
assert( initialized );
next_state.one -= __builtin_popcountll(h);
next_state.seg -= __builtin_popcountll(h^(h<<1));
long long g = h&(h<<1);
next_state.seg2 -= __builtin_popcountll(g^(g<<1));
h ^= 1ll<<col;
next_state.one += __builtin_popcountll(h);
next_state.seg += __builtin_popcountll(h^(h<<1));
g = h&(h<<1);
next_state.seg2 += __builtin_popcountll(g^(g<<1));
}
void flip(int r, int c, int len, int dir){
assert( initialized );
if( dir == 0 ){
assert(len+c <= n);
state.one -= __builtin_popcountll(H[r]);
state.seg -= __builtin_popcountll(H[r] ^ (H[r]<<1));
long long g = H[r]&(H[r]<<1);
state.seg2 -= __builtin_popcountll(g^(g<<1));
H[r] ^= ((1ll<<len)-1) << c;
state.one += __builtin_popcountll(H[r]);
state.seg += __builtin_popcountll(H[r] ^ (H[r]<<1));
g = H[r]&(H[r]<<1);
state.seg2 += __builtin_popcountll(g^(g<<1));
}else{
assert(len+r <= n);
for(int j=r; j<r+len; j++){
flip_cell(H[j], state, c);
}
}
}
vector< P > diff_one_row_col(int z, int len, int dir) {
assert( initialized );
vector< P > res(n-len+1, P{1ll<<58, 1ll<<58, 1ll<<58});
P next_state = state;
if(dir == 0){
long long hh = H[z];
for(int j=0; j<len; j++){
// auto tmp = next_state;
// auto hh_ = hh;
// flip_cell_dbg(hh_, tmp, j);
flip_cell(hh, next_state, j);
// if( tmp.seg2 != next_state.seg2 ){
// eprintln( tmp.seg2, next_state.seg2 );
// assert( tmp.seg2 == next_state.seg2 );
// }
}
res[0] = next_state;
for(int ub=len, lb=0; ub<n; ub++){
flip_cell(hh, next_state, ub);
flip_cell(hh, next_state, lb);
res[++lb] = next_state;
}
}else{
for(int j=0; j<len; j++){
// auto tmp = next_state;
// auto hh_ = H[j];
// flip_cell_dbg(hh_, tmp, z);
long long hh = H[j];
flip_cell(hh, next_state, z);
// if( tmp.seg2 != next_state.seg2 ){
// eprintln( tmp.seg2, next_state.seg2 );
// assert( tmp.seg2 == next_state.seg2 );
// }
}
res[0] = next_state;
for(int ub=len, lb=0; ub<n; ub++){
{
long long hl = H[lb] ^ (1ll<<z);
flip_cell(hl, next_state, z);
}
{
long long hu = H[ub];
flip_cell(hu, next_state, z);
}
res[++lb] = next_state;
}
}
return res;
}
bool one(int r, int c){
assert( initialized );
assert(0<=r && r<n);
assert(0<=c && c<n);
return (H[r]>>c)&1;
}
void init(){
state = P{0,0,0};
for(int i=0; i<n; i++){
state.one += __builtin_popcountll(H[i]);
long long y = H[i] ^ (H[i]<<1);
state.seg += __builtin_popcountll(y);
long long z = H[i] & (H[i]<<1);
state.seg2 += __builtin_popcountll( z^(z<<1) );
}
initialized = true;
}
int score() const {
assert( initialized );
return state.one;
}
double seg_score() const {
assert( initialized );
return (state.seg * 9.0) * 0.5 ;
}
double seg2_score() const {
assert( initialized );
return (state.seg * 9.0) * 0.5 ;
}
int score(const P& st) const {
assert( initialized );
return st.one;
}
double seg_score(const P& st) const {
assert( initialized );
return (st.seg * 9.0) * 0.5 ;
}
double seg2_score(const P& st) const {
assert( initialized );
return (st.seg * 9.0) * 0.5 ;
}
};
vector<long long> to_vector(const vector<string>& A){
vector<long long> res(n, 0);
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
res[i] |= (A[i][j] == '0' ? 1ll : 0ll) << j;
}
}
return res;
}
struct beam_state{
F f;
int vec_id;
int prv_id;
tuple<int,int,int> prv_move; // {r,c,dir}
};
struct Greedy{
vector<int> L;
double eval(double a, double b, double c, double t){
a = a*a + a * HyperParams::eval_a_1;
a *= (t + HyperParams::eval_a_t);
b = b*b * HyperParams::eval_b_2 + b * HyperParams::eval_b_1;
c = c*c * HyperParams::eval_c_2 + c * HyperParams::eval_c_1;
b = (b+c) * ( HyperParams::eval_b_tk * t + HyperParams::eval_b_t );
return a + b;
// return b * b * max<double>(0, 550-t) + 100.0 * a * a;
}
double put(F& f, vector<tuple<int,int,int>>& res, int id, double t, double drop = 0.0){
int len = L[id];
long long seg = (1ll<<len)-1;
using tt = tuple<double, int,int,int,int>;
tt nx(1e30, -1,-1,-1,-1);
for(int i=0; i<n; i++){
if( rng.prob() < drop ) continue;
auto tmp = f.diff_one_row_col(i, len, 0);
for(int j=0; j<tmp.size(); j++){
double a = f.score(tmp[j]);
double b = f.seg_score(tmp[j]);
double c = f.seg2_score(tmp[j]);
double w = eval(a,b,c,t);
tt cur(w, rng(1000000), i,j,0);
nx = min(nx, cur);
}
}
if( len > 1) for(int j=0; j<n; j++){
if( rng.prob() < drop ) continue;
auto tmp = f.diff_one_row_col(j,len,1);
for(int i=0; i<tmp.size(); i++){
double a = f.score(tmp[i]);
double b = f.seg_score(tmp[i]);
double c = f.seg2_score(tmp[i]);
double w = eval(a,b,c,t);
tt cur(w, rng(1000000), i,j,1);
nx = min(nx, cur);
}
}
double s;
int r,c,dir;
tie(s,ignore, r,c,dir) = nx;
if(r==-1){
r = 0;
c = 0;
dir = 0;
}
assert(r != -1);
res[id] = tuple<int,int,int>(r,c,dir);
f.flip(r,c,len,dir);
return s;
}
vector< tuple<double, int, int, tuple<int,int,int>> >
best_k(F& f, int id, double t, int k, int prv_id, double drop = 0.0){
int len = L[id];
long long seg = (1ll<<len)-1;
using movement = tuple<int,int,int>;
using tt = tuple<double, int, int, movement>; // score, rnd, prv, {r,c,dir}
priority_queue<tt, vector<tt>, less<tt>> q;
for(int i=0; i<n; i++){
if( rng.prob() < drop ) continue;
auto tmp = f.diff_one_row_col(i, len, 0);
for(int j=0; j<tmp.size(); j++){
double a = f.score(tmp[j]);
double b = f.seg_score(tmp[j]);
double c = f.seg2_score(tmp[j]);
double w = eval(a,b,c,t);
tt cur(w, rng(1000000), prv_id, movement(i,j,0));
q.push( cur );
if( q.size() > k ) q.pop();
}
}
if( len > 1) for(int j=0; j<n; j++){
if( rng.prob() < drop ) continue;
auto tmp = f.diff_one_row_col(j,len,1);
for(int i=0; i<tmp.size(); i++){
double a = f.score(tmp[i]);
double b = f.seg_score(tmp[i]);
double c = f.seg2_score(tmp[i]);
double w = eval(a,b,c,t);
tt cur(w, rng(1000000), prv_id, movement(i,j,1));
q.push( cur );
if( q.size() > k ) q.pop();
}
}
vector<tt> res;
while( q.size() ){
res.push_back( q.top() );
q.pop();
}
return res;
}
};
double solve(istream& is, bool printer = false, bool print_output = true){
my_time::init();
is >> n,k;
vector<int> L(k);
is >> L;
int max_len = *max_element(L.begin(), L.end());
vector<string> A(n);
is >> A;
vector<vector<int>> L_id(max_len+1);
for(int i=0; i<k; i++){
L_id[ L[i] ].push_back( i );
}
F initial_f;
initial_f.n = n;
initial_f.H =to_vector(A);
initial_f.init();
int first = initial_f.score();
eprintln(first);
vector<tuple<int,int,int>> res(k); //{r,c,dir}
vector<int> ids, unused_ids;
int lb = 3;
vector<int> rem(26);
for(int len=max_len; len>=1; len--){
for(int j=0; j<L_id[len].size(); j++){
int id = L_id[len][j];
if( len>lb ){
ids.push_back(id);
rem[len]++;
}else if(len==lb){
if( j < 3 ){
ids.push_back(id);
rem[len]++;
}else{
unused_ids.push_back(id);
}
}else{
unused_ids.push_back(id);
}
}
}
eprintln( my_time::getTime() , "sec");
int num_order_vec = 7;
vector<vector<double>> rank(num_order_vec, vector<double>(k));
for(int j=0; j<num_order_vec; j++){
for(int i=0; i<ids.size(); i++){
int len = L[ ids[i] ];
rank[j][ids[i]] = len * len * HyperParams::sort_len_2 + len * HyperParams::sort_len_1 + rng.prob();
}
}
vector<decltype(ids)> order_vec(num_order_vec, ids);
for(int j=0; j<num_order_vec; j++){
stable_sort(order_vec[j].begin(), order_vec[j].end(), [&](int a, int b){
return rank[j][a] > rank[j][b];
});
}
Greedy greedy;
greedy.L = L;
F best_f;
double score = 1e18;
// beam search
// vector<beam_state> state_pool;
// state_pool.reserve(10000);
// vector< vector<int> > beam_col(ids.size() + 1);
// {
// for(int i=0; i<num_order_vec; i++){
// beam_state st;
// st.f = initial_f;
// st.vec_id = i;
// st.prv_id = -1;
// state_pool.push_back( st );
// beam_col[0].push_back( state_pool.size()-1 );
// }
// }
// for(int col=0; col<ids.size(); col++){
// int next_w = max<int>(2, ceil(5 - (col*4.0)/ids.size()));
// if( col+1 == ids.size() ) next_w = 1;
// double t = (col+0.0) / ids.size();
// using movement = tuple<int,int,int>; // {r,c,dir}
// using small_state = tuple<double, int, int, movement>; // {score, rnd, prv, movement}
// priority_queue<small_state, vector<small_state>, less<small_state>> q;
// for(auto prv_id : beam_col[col]){
// auto& f = state_pool[prv_id].f;
// int vec_id = state_pool[prv_id].vec_id;
// int id = order_vec[vec_id][col];
// auto best_k = greedy.best_k(f, id, t, 2, prv_id, (ids.size() - col) * 0.4 / ids.size() );
// for(auto tmp : best_k){
// q.push(tmp);
// if(q.size() > next_w){
// q.pop();
// }
// }
// }
// while( q.size() ){
// auto tmp = q.top();
// q.pop();
// int prv_id;
// movement mv;
// tie(ignore, ignore, prv_id, mv) = tmp;
// F next_f = state_pool[prv_id].f;
// int vec_id = state_pool[prv_id].vec_id;
// int id = order_vec[vec_id][col];
// int r,c,dir;
// tie(r,c,dir) = mv;
// int len = L[id];
// next_f.flip(r,c, len, dir);
// beam_state st;
// st.f = next_f;
// st.vec_id = vec_id;
// st.prv_id = prv_id;
// st.prv_move = mv;
// state_pool.push_back( st );
// beam_col[ col+1 ].push_back( state_pool.size() - 1 );
// // if(q.size() == 0){
// // eprintln("col #", col, ":", st.f.score());
// // }
// }
// }
// eprintln( my_time::getTime() , "sec");
// {
// int cur_id = beam_col[ids.size()].back();
// auto& st = state_pool[cur_id];
// int vec_id = st.vec_id;
// best_f = st.f;
// ids = order_vec[vec_id];
// for(int col = ids.size()-1; col>=0; col--){
// int id = ids[col];
// res[id] = state_pool[ cur_id ].prv_move;
// cur_id = state_pool[ cur_id ].prv_id;
// }
// }
// score = best_f.score();
vector<decltype(res)> res__(num_order_vec, res);
for(int j=0; j<num_order_vec; j++){
F g = initial_f;
for(int t=0; t<order_vec[j].size(); t++){
int id = order_vec[j][t];
greedy.put(g, res__[j], id, t * 1.0 / order_vec[j].size(), 0.1 );
}
double score_ = g.score();
if(score > score_){
eprintln("score :", score, "->", score_);
score = score_;
best_f = g;
res = res__[j];
ids = order_vec[j];
}
}
eprintln( my_time::getTime() , "sec");
eprintln( best_f.score() );
vector<tuple<int,int,int>> best = res;
double best_score = score;
int num_itr = 0;
int best_update = 0;
F f = best_f;
for(;;num_itr++){
if( my_time::getTime() > 0.97 ) break;
F f_ = f;
auto res_ = res;
int prev_score = f_.score();
vector<int> popped;
int m = rng(5) + 1;
for(int i=0; i<m; i++){
int j = rng( ids.size() - i ) + i;
swap(ids[i], ids[j]);
int id = ids[i];
popped.push_back(id);
int r,c,dir;
tie(r,c,dir) = res[id];
f_.flip(r,c,L[id],dir);
}
int r = m;
for(int id : popped){
greedy.put(f_,res,id, 1.0 - r*0.01, r * 0.2 / m );
r--;
}
int next_score = f_.score();
int diff = next_score - best_score;
if( diff <= 0 ){
if( next_score < best_score ){
// eprintln("best :", best_score, "->", next_score, ":", m);
// for(int j : popped){
// eprint(L[j], "");
// }eprintln("");
best_score = next_score;
best = res;
best_update++;
}
f = f_;
}else{
res = res_;
}
}
eprintln( my_time::getTime() , "sec");
eprintln( "num_itr = ", num_itr );
eprintln( "best_update = ", best_update );
eprintln( "score = ", best_score );
F g = initial_f;
res = best;
for(auto id : ids){
int r,c,dir;
tie(r,c,dir) = res[id];
int len = L[id];
g.flip(r,c,len,dir);
}
eprintln( my_time::getTime() , "sec");
for(auto id : unused_ids){
greedy.put(g, res, id, 0.9999 );
}
eprintln( my_time::getTime() , "sec");
best_score = g.score();
if( print_output ){
for(int i=0; i<k; i++){
int r,c,dir;
tie(r,c,dir) = res[i];
int len = L[i];
print( r+1, c+1, r+(dir?len:1), c+(dir?1:len) );
print("\n");
}
}
// {
// vector<vector<int>> hor(n), var(n);
// for(int i=0; i<k; i++){
// if( get<2>(res[i]) == 0 ) hor[ get<0>(res[i]) ].push_back( L[i] );
// if( get<2>(res[i]) == 1 ) var[ get<1>(res[i]) ].push_back( L[i] );
// }
// eprintln("horizontal:");
// for(int i=0; i<n; i++){
// eprint("row ", i, ":\t");
// sort(hor[i].rbegin(), hor[i].rend());
// eprintln(hor[i]);
// }
// eprintln("vartical:");
// for(int i=0; i<n; i++){
// eprint("col ", i, ":\t");
// sort(var[i].rbegin(), var[i].rend());
// eprintln(var[i]);
// }
// }
eprintln( my_time::getTime() , "sec");
if(printer){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
eprint( g.one(i,j) ? '#' : '.' );
}eprintln("");
}
}
eprintln("score = ", best_score );
eprintln("diff score = ", best_score - first);
return best_score - first;
}
}
double get_double(char* in){
stringstream ss(in);
double res;
ss >> res;
return res;
}
int main(int argc, char* argv[]){
#ifdef LOCAL_TEST
vector<int> seed;
map<string, double*> args = {
{"-sort_len_2", &HyperParams::sort_len_2},
{"-sort_len_1", &HyperParams::sort_len_1},
{"-eval_a_2", &HyperParams::eval_a_2},
{"-eval_a_1", &HyperParams::eval_a_1},
{"-eval_a_t", &HyperParams::eval_a_t},
{"-eval_b_2", &HyperParams::eval_b_2},
{"-eval_b_1", &HyperParams::eval_b_1},
{"-eval_c_2", &HyperParams::eval_c_2},
{"-eval_c_1", &HyperParams::eval_c_1},
{"-eval_b_tk", &HyperParams::eval_b_tk},
{"-eval_b_t", &HyperParams::eval_b_t}
};
for(int i=1; i<argc; i++){
if( argv[i] == "-seed"s ){
if(i+1<argc){
int s;
sscanf(argv[i+1],"%d", &s);
seed.push_back(s);
i++;
}
}
for(auto arg_set : args){
if( argv[i] == arg_set.first && i+1 < argc ){
*(arg_set.second) = get_double( argv[++i] );
eprintln( arg_set.first, " = ", *(arg_set.second) );
break;
}
}
}
if(seed.size()){
auto in = generator(seed[0]);
stringstream input(in);
// eprintln(in);
double res = Solver::solve(input, false, false);
println(res);
return 0;
}
double sum = 0;
for(int seed=1; seed<=32; seed++){
stringstream input(generator(seed));
sum += Solver::solve(input, false, false);
eprintln("seed = ", seed);
eprintln("sum = ", sum/(seed+0.0)*32.0 );
eprintln("ave = ", sum/(seed+0.0) );
}
eprintln("sum = ", sum);
eprintln("ave = ", sum/32.0);
println(sum);
#else
auto& input = cin;
Solver::solve(input);
#endif
return 0;
}