結果

問題 No.5002 stick xor
ユーザー gurualogurualo
提出日時 2018-05-26 23:47:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 8,846 bytes
コンパイル時間 6,318 ms
実行使用メモリ 2,548 KB
スコア 0
最終ジャッジ日時 2018-05-26 23:47:37
ジャッジサーバーID
（参考情報） 		judge9 /
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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_


#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=2980;

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;
}
int bestscore;
vector<A> SA() {

	vector<A> bestAnss = anss;
	bestscore = score;
	LL t;
	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);
		}
		//dump(Temp);
		//if (Temp < endTemp) { startTemp *= 0.99; Temp = startTemp; }
	}


	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++; }
	}
	
#endif
	cerr << "initW " << initW << endl;
	cerr << "nowW " << bestscore << endl;
	//ASSERT((W) == bestscore);
	cerr << "Score = " << bestscore - initW << endl;
#ifndef LOCAL

	REP(i, K) {
		//cout << ret_ans(anss[i]) << endl;
		cout << anss[i] << endl;
	}
#endif
}
0