結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-26 16:20:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 933 ms / 1,000 ms |
コード長 | 6,268 bytes |
コンパイル時間 | 34,127 ms |
実行使用メモリ | 64,228 KB |
スコア | 38,091 |
最終ジャッジ日時 | 2018-05-26 16:20:54 |
ジャッジサーバーID (参考情報) |
judge9 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
// C++11#define _DEBUG#define DEBUG2#define _DEBUG3#include <algorithm>#include <cstdlib>#include <iostream>#include <vector>#include <cmath>#include "bits/stdc++.h"#include <sys/time.h>#include <emmintrin.h>#include <string>#include <bitset>using namespace std;inline long long GetTSC() {long long lo, hi;asm volatile ("rdtsc": "=a"(lo), "=d"(hi));return lo + (hi << 32);}inline double GetSeconds() {return GetTSC() / 2.8e9;}class XRand{public:unsigned int x, y, z, w;const int DC = pow(2, 27);XRand() { init(); }void init() { x = 314159261; y = 358979323; z = 846264338; w = 327950288; }unsigned int next() { unsigned int t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8; }int nextInt(int m) { return (int)(next() % m); }double nextDouble() { return double(next() % DC) / DC; }};const double TO = 0.85;const int NM = 60;const int NMM = NM * NM;const int KM = 500;bitset<NMM> A;bitset<NMM> mask[26][NMM * 2];int mi[26];int RI[KM];int L[KM];int R[KM][4];double starttime, gt;XRand rnd = XRand();#ifdef DEBUGstruct XorShift {uint64_t x = 88172645463325252ULL;XorShift() {}void setSeed(uint64_t seed) {x = seed;}uint64_t next() {x ^= x << 13;x ^= x >> 7;x ^= x << 17;return x;}int nextInt(int n) {uint64_t upper = 0xFFFFFFFFFFFFFFFFULL / n * n;uint64_t v = next();while (v >= upper) {v = next();}return v % n;}double nextDouble() {uint64_t v = next() >> 11; // 53bitreturn (double)v / (1ULL << 53);}};XorShift xs;int p_seed;bitset<NM*NM> p_a;bitset<NM*NM> p_a_init;int p_l[KM];class PlayMachine {public:static void init(int i){p_seed = i;xs.setSeed(p_seed);p_a_init.reset();p_a.reset();for(int i=0; i<NMM; i++){p_a_init[i] = xs.nextInt(2);}for(int i=0; i<KM; i++){p_l[i] = xs.nextInt(25) + 1;}}static int calc_score(){p_a = p_a_init;for(int i=0; i<KM; i++){int a,b,c,d;a = R[i][0];b = R[i][1];c = R[i][2];d = R[i][3];int l = p_l[i];if((a == c && d-b+1 == l) || (b == d && c-a+1 == l)){for(int j=a; j<=c; j++){for(int k=b; k<=d; k++){p_a[j*NM+k] = 1 - p_a[j*NM+k];}}}else{cout << "err i: " << i << " l: " << l << " a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;}}cout << p_seed << " " << (p_a_init.count() - p_a.count()) << endl;return p_a_init.count() - p_a.count();}static void print(){int score = calc_score();#ifdef DEBUG2cerr << "60 500" << endl;for(int i=0; i<KM; i++){cerr << p_l[i] << " ";}cerr << endl;cerr << endl;for(int i=0; i<NM; i++){for(int j=0; j<NM; j++){cerr << p_a_init[i*NM+j];}cerr << endl;}cerr << endl;for(int i=0; i<NM; i++){for(int j=0; j<NM; j++){cerr << p_a[i*NM+j];}cerr << endl;}cerr << endl;#endifcerr << "score: " << score << endl;}};#endifvoid solve(){starttime = GetSeconds();// input#ifdef DEBUGA = p_a_init;for(int i=0; i<KM; i++){L[i] = p_l[i];}#elseint n,k;cin >> n >> k;for(int i=0; i<k; i++){cin >> L[i];}for(int i=0; i<n; i++){string s;cin >> s;for(int j=0; j<n; j++){A[i*NM+j] = s[j] == '1';}}#endif// initfor(int i=1; i<26; i++){mi[i] = 0;auto ma = mask[i];for(int j=0; j<NM; j++){for(int k=0; k<NM; k++){if(j <= NM-i){ma[mi[i]].reset();for(int l=0; l<i; l++){ma[mi[i]][(j+l)*NM+k] = 1;}mi[i]++;}if(k <= NM-i && i > 1){ma[mi[i]].reset();for(int l=0; l<i; l++){ma[mi[i]][j*NM+k+l] = 1;}mi[i]++;}}}ma[mi[i]].reset();}for(int l=25; l>0; l--){auto ma = mask[l];int mm = mi[l];for(int i=0; i<KM; i += rnd.nextInt(2) + 1){if(L[i] != l) continue;int ti = 0;int tm = -30;for(int j=0; j<mm; j += rnd.nextInt(2) + 1){int tc = (A & ma[j]).count();if(tc > tm){tm = tc;ti = j;}}RI[i] = ti;A ^= ma[RI[i]];}}int cc = A.count();#ifdef DEBUG2cerr << "bcc: " << cc << endl;#endifint tt = 0;while(1){double gt = (GetSeconds() - starttime) / TO;if(gt >= 1.0) break;int i = tt % KM;int l = L[i];int ri = RI[i];auto ma = mask[l];int mii = mi[l];int ni = rnd.nextInt(mii - 1);if(ni >= ri) ni++;int nc = (A ^ ma[ri] ^ ma[ni]).count();if(nc <= cc || rnd.nextDouble() / pow(nc - cc, 2) > gt){RI[i] = ni;cc = nc;A ^= ma[ri] ^ ma[ni];}else{}tt++;}#ifdef DEBUG2cerr << "acc: " << cc << endl;#endif// outputfor(int i=0; i<KM; i++){int l = L[i];int ri = RI[i];auto ms = mask[l][ri];for(int j=0; j<NMM; j++){if(!ms[j]) continue;R[i][0] = j / NM;R[i][1] = j % NM;R[i][2] = j / NM;R[i][3] = j % NM;if(j+1 < NMM && ms[j+1]) R[i][3] += l - 1;if(j+NM < NMM && ms[j+NM]) R[i][2] += l - 1;break;}}cerr << "tt: " << tt << ", time: " << (GetSeconds() - starttime) << endl;}#ifdef DEBUG#ifdef DEBUG2const int TEST_MAX = 1;#elseconst int TEST_MAX = 10;#endifint main() {srand((unsigned) time(NULL));double total = 0;for(int i=1; i<=TEST_MAX; i++){#ifdef DEBUG2PlayMachine::init(10);#elsePlayMachine::init(i);#endifsolve();#ifdef DEBUG2PlayMachine::print();}#elseint score = PlayMachine::calc_score();total += score;}cerr << "avg: " << total / TEST_MAX << endl;#endifreturn 0;}#elseint main(){solve();for(int i=0; i<KM; i++){cout << R[i][0] + 1;for(int j=1; j<4; j++){cout << " " << R[i][j] + 1;}cout << endl;}return 0;}#endif