#260792 (C++14) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: gurualo
• 提出日時: 2018-05-27 11:12:43
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 996 ms / 1,000 ms
• コード長: 8,926 bytes
• コンパイル時間: 36,160 ms
• 実行使用メモリ: 1,660 KB
• スコア: 36,483
• 最終ジャッジ日時: 2018-05-27 11:13:21
• ジャッジサーバーID （参考情報）: judge9 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	991 ms; 1,612 KB
testcase_01	AC	991 ms; 1,612 KB
testcase_02	AC	996 ms; 1,612 KB
testcase_03	AC	991 ms; 1,608 KB
testcase_04	AC	991 ms; 1,612 KB
testcase_05	AC	991 ms; 1,616 KB
testcase_06	AC	991 ms; 1,608 KB
testcase_07	AC	990 ms; 1,612 KB
testcase_08	AC	991 ms; 1,612 KB
testcase_09	AC	996 ms; 1,656 KB
testcase_10	AC	992 ms; 1,612 KB
testcase_11	AC	991 ms; 1,612 KB
testcase_12	AC	996 ms; 1,612 KB
testcase_13	AC	992 ms; 1,616 KB
testcase_14	AC	991 ms; 1,616 KB
testcase_15	AC	991 ms; 1,616 KB
testcase_16	AC	991 ms; 1,616 KB
testcase_17	AC	991 ms; 1,660 KB
testcase_18	AC	990 ms; 1,612 KB
testcase_19	AC	991 ms; 1,608 KB
testcase_20	AC	991 ms; 1,608 KB
testcase_21	AC	990 ms; 1,616 KB
testcase_22	AC	991 ms; 1,616 KB
testcase_23	AC	991 ms; 1,616 KB
testcase_24	AC	991 ms; 1,656 KB
testcase_25	AC	990 ms; 1,612 KB
testcase_26	AC	990 ms; 1,660 KB
testcase_27	AC	992 ms; 1,612 KB
testcase_28	AC	991 ms; 1,608 KB
testcase_29	AC	990 ms; 1,608 KB
testcase_30	AC	991 ms; 1,612 KB
testcase_31	AC	991 ms; 1,608 KB

ソースコード

#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=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,besttable;
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;
	besttable = table;
	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;
				besttable = table;
			}
		}
		else {
			//元に戻す
			domove(b);
			domove(a);
		}
		//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 << besttable << 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();

	
	
#endif
	cerr << "initW " << initW << endl;
	cerr << "nowW " << bestscore << endl;
	W = 0;
	REP(i, N)REP(j, N) {
		//table[i][j] = Adice(mt;
		if (besttable[i][j] == 0) { W++; }
	}
	ASSERT(W == bestscore);
	cerr << "Score = " << bestscore - initW << endl;
#ifndef LOCAL

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