結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 gurualo
|
| 提出日時 | 2018-05-26 23:32:59 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,850 bytes |
| コンパイル時間 | 35,871 ms |
| 実行使用メモリ | 1,644 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2018-05-26 23:33:39 |
|
ジャッジサーバーID （参考情報） |
judge8 / |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 32 |
ソースコード
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <set>
#include <string>
#include <random>
#include <iomanip>
#include <cstring>
#include <fstream>
//#define LOCAL
using namespace std;
typedef vector<int> VI;
typedef vector< VI > VVI;
typedef int64_t LL;
typedef vector<double> VD;
//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
//container util
//------------------------------------------
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define LOG_
//
//#ifdef LOG_
//#define LOG(x) cerr << #x << " = " << (x) << endl;
//#else
//#define LOG(x) ((void)0);
//#endif
#if defined(__GNUC__)
#include <assert.h>
#define ASSERT_(x) assert(x)
#else
#include <assert.h>
#define ASSERT_(x) assert(x)
#endif
//#define _DEBUG
#ifdef _DEBUG
#define dump(x) cerr << #x << '=' << (x) << endl;
#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;
#define ASSERT(x) {if (!(x)){std::cout << "\nError!!\n" << "info string file:" << __FILE__ << " line:" << __LINE__ <<" "<< #x<< std::endl;ASSERT_(x);}}
#endif
#ifndef _DEBUG
//#define ASSERT(X) { if (!(X)){std::cout << "\nError!!\n" << "info string file:" << __FILE__ << " line:" << __LINE__ <<" "<< #X<< std::endl; *(int*)1 =0;} }
#define ASSERT(x) ((void)0)
#define debug(x) ((void)0)
#define dump(x) ((void)0)
#endif
#define CLR(a) memset((a), 0 ,sizeof(a))
unsigned long xor128() {
static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned long t = (x ^ (x << 11));
x = y; y = z; z = w;
return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
unsigned long randomWrapper() {
return xor128();
}
#if defined(__GNUC__)
#include <sys/time.h>
#include <immintrin.h>
#include <string.h>
LL starttime;
inline LL now() {
struct timeval tv;
gettimeofday(&tv, NULL);
LL t = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
return t;
}
inline LL elapsed() { return now() - starttime; }
#else
#include <chrono>
#include <intrin.h>
typedef std::chrono::milliseconds::rep TimePoint;
inline TimePoint now() { return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now().time_since_epoch()).count(); }
TimePoint starttime;
inline TimePoint elapsed() { return now() - starttime; }
#endif
LL Maxtime=980;
std::mt19937 get_rand_mt;
class matrix : public vector< vector<char> > {
private:
int tate_, yoko_;
public:
matrix(const int tate__, const int yoko__) {
assert(tate__ > 0); assert(yoko__ > 0);
resize(tate__);
for (size_t i = 0; i < size(); i++) { (*this)[i].resize(yoko__); }
tate_ = tate__; yoko_ = yoko__;
}
matrix() {};
int tate()const { return tate_; }
int yoko()const { return yoko_; }
void resizematrix(const int tate__, const int yoko__) {
assert(tate__ > 0); assert(yoko__ > 0);
resize(tate__);
for (size_t i = 0; i < size(); i++) {
(*this)[i].resize(yoko__);
}
tate_ = tate__; yoko_ = yoko__;
}
void setone() {
for (int i = 0; i<tate(); i++) for (int j = 0; j < yoko(); j++) { (*this)[i][j] = 1; }
}
void setzero() {
for (int i = 0; i<tate(); i++) for (int j = 0; j < yoko(); j++) { (*this)[i][j] = 0; }
}
};
inline std::ostream & operator<<(std::ostream & os, const matrix & m)
{
for (int j = 0; j < m.tate(); j++) {
os << "[";
for (int i = 0; i < m.yoko(); i++) {
// os.precision(3);
os <<m[j][i];
}
os << "]" << endl;
}
return os;
}
#define LOCAL
int N = 60;
int K = 500;
matrix table;
vector<int> Ls;
//
//const int maskfromy = 0b1111111;
//const int maskfromx = maskfromy << 8;
//const int masktoy = maskfromy << 16;
//const int masktox = 0b1111111<<24;
//
//int32_t make_ans(int fromy, int fromx, int toy, int tox) {
// int32_t a = fromy;
// a |= (fromx << 8);
// a |= (toy << 16);
// a |= (tox << 24);
// return a;
//}
//
//string ret_ans(int32_t a) {
// string s;
// s += toString(a&maskfromy) + " " + toString(int(a&maskfromx)) + " " + toString(a&masktoy) + " " + toString(a&masktox);
// return s;
//}
struct A
{
int fromx,fromy;int tox , toy;
};
vector<A> anss;
//vector<int32_t> anss;
inline std::ostream & operator<<(std::ostream & os, const A & a)
{
os << a.fromy+1 << " " << a.fromx+1 << " " << a.toy+1<<" " << a.tox+1;
return os;
}
//#define LOG_
int initW = 0, W = 0, score = 0;
//Xorなので2回動作させると元に戻る
void domove(int fromy,int fromx,int toy,int tox) {
if (fromx == tox) {
for (int y = fromy; y <= toy; y++) {
table[y][fromx] ^= 1;
(table[y][fromx] == 1) ? score-- : score++;
}
}
else if (fromy == toy) {
for (int x = fromx; x <= tox; x++) {
table[fromy][x] ^= 1;
(table[fromy][x] == 1) ? score-- : score++;
}
}
else {
ASSERT(0);
}
}
void domove(const A& a) {
domove(a.fromy, a.fromx, a.toy, a.tox);
}
A makemoveRand(int length) {
A a;
int fromx = randomWrapper() % (N - length);
int fromy = (randomWrapper() % N);
//int fromy = 0;
int tox = fromx + length - 1, toy = fromy;
//int32_t a = make_ans(fromy, fromx, toy, tox);
//cerr << a << endl;
if (double(randomWrapper() % 6000) / 6000.0 < 0.5) {
swap(fromx, fromy);
swap(tox, toy);
}
a.fromx = fromx;
a.fromy = fromy;
a.toy = toy;
a.tox = tox;
return a;
}
vector<A> SA() {
vector<A> bestAnss = anss;
int bestscore = score;
LL t;
const double startTemp = 100;
const double endTemp = 10;
double cool = 0.99;
double Temp = startTemp;
while ((t=elapsed())<Maxtime)
{
int oldscore = score;
int index = randomWrapper()%SZ(anss);
//anss[index]での操作を巻き戻し
A a = anss[index];
domove(a);
//あたらしいmoveでスコアを計算
A b = makemoveRand(Ls[index]);
domove(b);
int newscore = score;
//Temp = startTemp + (endTemp - startTemp)*t / Maxtime;
Temp *= cool;
bool force = exp((newscore - oldscore) / Temp) > (double)(randomWrapper() % 10000) / 10000.0;
bool better = newscore > bestscore;
if (force||better) {
anss[index] = b;
if (better) {
bestscore = newscore;
bestAnss = anss;
}
}
else {
//元に戻す
domove(b);
}
}
return bestAnss;
}
void solve() {
anss.resize(K);
//make ans
REP(i, K) {
int fromx = randomWrapper() % (N - Ls[i]);
int fromy = (randomWrapper() % N);
//int fromy = 0;
int tox = fromx + Ls[i] - 1, toy = fromy;
//int32_t a = make_ans(fromy, fromx, toy, tox);
//cerr << a << endl;
if (double(randomWrapper() % 6000) / 6000.0 < 0.5) {
swap(fromx, fromy);
swap(tox, toy);
}
anss[i].fromx = fromx;
anss[i].fromy = fromy;
anss[i].toy = toy;
anss[i].tox = tox;
}
score = initW;
//do_ans
REP(i, K) {
domove(anss[i].fromy,
anss[i].fromx,
anss[i].toy,
anss[i].tox
);
}
anss=SA();
cerr << table << endl;
}
int main(int argc, char *argv[]) {
starttime = now();
int seed = 0;
if (argc >= 2) {
seed = toInt(argv[1]);
}
#ifdef LOG_
string input = "./data/input" + toString(seed) + ".txt";
string output = "./data/output" + toString(seed) + ".txt";
#endif
#ifdef LOCAL
//MakeTestCase maketest;
std::random_device rd;
std::mt19937 mt(seed);
table.resizematrix(N, N);
Ls.resize(K);
std::uniform_int_distribution<int> Adice(0, 1);
std::uniform_int_distribution<int> Ldice(1, 25);
REP(i, N)REP(j, N) {
table[i][j] = Adice(mt);
if (table[i][j] == 0) { initW++; }
}
REP(i, K) {
Ls[i] = Ldice(mt);
}
#else
cin >> N >> K;
table.resizematrix(N, N);
Ls.resize(K);
REP(i, K) {
cin >> Ls[i];
}
REP(i, N){
string s;
cin>>s;
dump(s);
REP(j, N) {
table[i][j] = (s[j]-'0');
}
}
#endif
#ifdef LOG_
ofstream ofs(input);
ofs<<toString(N) + " " + toString(K) + "\n";
REP(i, K) {
ofs<<toString(Ls[i]) + " ";
}
ofs<< "\n";
REP(i, N) {
REP(j, N) {
ofs<< toString((int)table[i][j]) + "";
}
ofs<< "\n";
}
ofs.close();
#endif
solve();
//ret ans
#ifdef LOG_
ofstream ofs2(output);
REP(i, K) {
//ofs2 << ret_ans(anss[i]) << endl;
ofs2 << anss[i] << endl;
}
ofs2.close();
REP(i, N)REP(j, N) {
//table[i][j] = Adice(mt;
if (table[i][j] == 0) { W++; }
}
cerr << "initW " << initW << endl;
cerr << "nowW " << W << endl;
ASSERT((W) == score);
cerr << "Score = " << score-initW << endl;
#endif
#ifndef LOCAL
REP(i, K) {
//cout << ret_ans(anss[i]) << endl;
cout << anss[i] << endl;
}
#endif
}