#define NDEBUG #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; namespace { using Integer = long long; //__int128; template istream& operator >> (istream& is, pair& p){return is >> p.first >> p.second;} template istream& operator >> (istream& is, vector& vec){for(T& val: vec) is >> val; return is;} template istream& operator , (istream& is, T& val){ return is >> val;} template ostream& operator << (ostream& os, const pair& p){return os << p.first << " " << p.second;} template ostream& operator << (ostream& os, const vector& vec){for(size_t i=0; i ostream& operator , (ostream& os, const T& val){ return os << " " << val;} template void print(const H& head){ cout << head; } template void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); } template void println(const T& ... values){ print(values...); cout << endl; } template void eprint(const H& head){ cerr << head; } template void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); } template 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::steady_clock::now().time_since_epoch()).count()); template string join(const vector& v, const string& sep){ stringstream ss; for(size_t i=0; i0) 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(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 T& operator()(vector& 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 L(k); XorShift rng(seed); for(auto& l : L) l = rng(25) + 1; vector 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 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 = (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< 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>c)&1; } void init(){ state = P{0,0,0}; for(int i=0; i to_vector(const vector& A){ vector res(n, 0); for(int i=0; i prv_move; // {r,c,dir} }; struct Greedy{ vector 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(0, 550-t) + 100.0 * a * a; } double put(F& f, vector>& res, int id, double t, double drop = 0.0){ int len = L[id]; long long seg = (1ll<; tt nx(1e30, -1,-1,-1,-1); for(int i=0; i 1) for(int j=0; j(r,c,dir); f.flip(r,c,len,dir); return s; } vector< tuple> > 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<; using tt = tuple; // score, rnd, prv, {r,c,dir} priority_queue, less> q; for(int i=0; i k ) q.pop(); } } if( len > 1) for(int j=0; j k ) q.pop(); } } vector 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 L(k); is >> L; int max_len = *max_element(L.begin(), L.end()); vector A(n); is >> A; vector> L_id(max_len+1); for(int i=0; i> res(k); //{r,c,dir} vector ids, unused_ids; int lb = 3; vector rem(26); for(int len=max_len; len>=1; len--){ for(int j=0; jlb ){ 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> rank(num_order_vec, vector(k)); for(int j=0; j order_vec(num_order_vec, ids); for(int j=0; j rank[j][b]; }); } Greedy greedy; greedy.L = L; F best_f; double score = 1e18; // beam search // vector state_pool; // state_pool.reserve(10000); // vector< vector > beam_col(ids.size() + 1); // { // for(int i=0; i(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; // {r,c,dir} // using small_state = tuple; // {score, rnd, prv, movement} // priority_queue, less> 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 res__(num_order_vec, res); for(int j=0; j 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> 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 popped; int m = rng(5) + 1; for(int i=0; i", 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> hor(n), var(n); // for(int i=0; i(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