結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-06-01 14:05:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#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(){ returnrange_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-indexedmt19937 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_TESTnamespace 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_TESTvector<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);#elseauto& input = cin;Solver::solve(input);#endifreturn 0;}