結果

問題 No.5002 stick xor
ユーザー iehniehn
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// 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 DEBUG
struct 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; // 53bit
return (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 DEBUG2
cerr << "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;
#endif
cerr << "score: " << score << endl;
}
};
#endif
void solve(){
starttime = GetSeconds();
// input
#ifdef DEBUG
A = p_a_init;
for(int i=0; i<KM; i++){
L[i] = p_l[i];
}
#else
int 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
// init
for(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 DEBUG2
cerr << "bcc: " << cc << endl;
#endif
int 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 DEBUG2
cerr << "acc: " << cc << endl;
#endif
// output
for(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 DEBUG2
const int TEST_MAX = 1;
#else
const int TEST_MAX = 10;
#endif
int main() {
srand((unsigned) time(NULL));
double total = 0;
for(int i=1; i<=TEST_MAX; i++){
#ifdef DEBUG2
PlayMachine::init(10);
#else
PlayMachine::init(i);
#endif
solve();
#ifdef DEBUG2
PlayMachine::print();
}
#else
int score = PlayMachine::calc_score();
total += score;
}
cerr << "avg: " << total / TEST_MAX << endl;
#endif
return 0;
}
#else
int 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0