Submission #1868131

---

Source Code Expand

// C++11
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <iostream>
#define SUBMIT
//#define BATCH
#ifndef SUBMIT

template < typename T > std::string to_string(const T& n)
{
	std::ostringstream stm;
	stm << n;
	return stm.str();
}

#endif // !SUBMIT

using namespace std;
#ifdef SUBMIT
const int64_t CYCLES_PER_SEC = 2800000000;
#else
const int64_t CYCLES_PER_SEC = 2500000000;
#endif
const double TIMELIMIT_SA = 29;
const double TIMELIMIT_GREEDY = 5;
struct Timer {
	int64_t start;
	Timer() { reset(); }
	void reset() { start = getCycle(); }
	void plus(double a) { start -= (a * CYCLES_PER_SEC); }
	inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
	inline int64_t getCycle() {
		uint32_t low, high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((int64_t)low) | ((int64_t)high << 32);
	}
};
class XorShift {
public:
	unsigned int x, y, z, w;
	double nL[65536];

	XorShift()
	{
		init();
	}

	void init()
	{
		x = 314159265; y = 358979323; z = 846264338; w = 327950288;
		double n = 1 / (double)(2 * 65536);
		for (int i = 0; i < 65536; ++i) {
			nL[i] = log(((double)i / 65536) + n);
		}
	}

	inline unsigned int next()
	{
		unsigned int t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
	}

	inline double nextLog() {
		return nL[next() & 0xFFFF];
	}

	inline int nextInt(int m)
	{
		return (int)(next() % m);
	}


	int nextInt(int min, int max)
	{
		return min + nextInt(max - min + 1);
	}


	double nextDouble()
	{
		return (double)next() / ((long long)1 << 32);
	}


};
XorShift rnd;
XorShift genrnd;
Timer timer;
vector<vector<int> > mat;
vector<vector<int> > ed;

int N, M;
int V;
int E;
int inputcnt = 0;
#ifdef SUBMIT
void input() {
	cin >> N >> M;
	E = M;
	mat.resize(N, vector<int>(N, 0));
	//ed.resize(N);
	//va.resize(N);
	int a, b, c;
	for (int i = 0; i < M; ++i) {
		cin >> a >> b;
		a--;
		b--;
		mat[a][b] = 1;
		mat[b][a] = 1;
		//ed[a].push_back(b);
		//va[a].push_back(c);
		//ed[b].push_back(a);
		//va[b].push_back(c);
	}
	int t;
	cin >> V >> t;
	V = (int)(sqrt(V) + 0.1);
	for (int i = 0; i < t; ++i) {
		cin >> a >> b;
	}
}
#else
void init() {
	mat.clear();
	timer.reset();
}
void input() {

	N = genrnd.nextInt(496) + 5;
	mat.resize(N, vector<int>(N, 0));
	int c;
	int nn = genrnd.nextInt(N, min(20000, (N - 1)*N / 2));
	int ii, jj;
	E = 0;
	for (int i = 1; i < N; i++) {
		ii = i;
		jj = genrnd.nextInt(i);
		if (mat[ii][jj] == 0 && ii != jj) {
			mat[ii][jj] = 1;
			mat[jj][ii] = 1;
			E++;
		}
	}
	while (E < nn) {
		ii = genrnd.nextInt(N);
		jj = genrnd.nextInt(N);
		if (mat[ii][jj] == 0 && ii != jj) {
			mat[ii][jj] = 1;
			mat[jj][ii] = 1;
			E++;
		}
	}



	while (true) {
		V = genrnd.nextInt(60) + 1;
		if (V*V >= N) break;
	}
	inputcnt++;
	//V = 5;
}
#endif
inline bool isvalid(int x, int y) {
	return x >= 0 && y >= 0 && x < V && y < V;
}
vector<vector<int> > ne;
void setps() {
	ed.clear();
	ed.resize(N);
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (mat[i][j] > 0) {
				ed[i].push_back(j);
			}
		}
	}
	ne.clear();
	ne.resize(V*V);
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			for (int ii = i - 1; ii <= i + 1; ii++) {
				for (int jj = j - 1; jj <= j + 1; jj++) {
					if (ii != i || jj != j) {
						if (isvalid(ii, jj)) {
							ne[i*V + j].push_back(ii*V + jj);
						}
					}
				}
			}
		}
	}
}


int getScore(vector<int> &od) {
	int score = 0;
	vector<vector<int> >mpe(N, vector<int>(N, 0));
	int a;
	for (int pos = 0; pos < V*V; ++pos) {
		a = od[pos];
		if (a != -1) {
			for (int i = 0; i < ne[pos].size(); i++) {
				if (od[ne[pos][i]] != -1) {
					if (mat[a][od[ne[pos][i]]] == 1) {
						if (a < od[ne[pos][i]]) {
							if (mpe[a][od[ne[pos][i]]] == 0) {
								score++;
							}
							mpe[a][od[ne[pos][i]]]++;
						}
						else if (a > od[ne[pos][i]]) {
							if (mpe[od[ne[pos][i]]][a] == 0) {
								score++;
							}
							mpe[od[ne[pos][i]]][a]++;
						}
					}
				}
			}
		}
	}
	return score;
}
//struct stateSA {
//
//};
vector<vector<int> > mp;
vector<int> od;
vector<int> edc;
vector<int> root;
vector<int> scp;
vector<int> wh;
vector<int> ud1;
vector<int> ud2;
vector<int> ud3;

vector<vector<int> > updated;
//vector<vector<int> > uval;
vector <vector<int> > res;
int upd;
inline void undo() {
	for (int i = (int)ud1.size() - 1; i >= 0; i--) {
		mp[ud1[i]][ud2[i]] = ud3[i];
		mp[ud2[i]][ud1[i]] = ud3[i];
	}	
}
inline int putdiff(int a, int pos) {
	int ret = -1;
	od[pos] = a;
	int g;
	for (int i = 0; i < ne[pos].size(); i++) {
		g = od[ne[pos][i]];
		if (g != -1) {
			if (mat[a][g] == 1) {
				if (mp[a][g] == 0) {
					ret += 100;
				}
				if (updated[a][g] != upd) {
					updated[a][g] = upd;
					ud1.push_back(a);
					ud2.push_back(g);
					ud3.push_back(mp[a][g]);
				}
				mp[a][g]++;
				mp[g][a]++;
				
			}
		}
	}
	return ret;
}
inline void put(int a, int pos, int rt) {

	od[pos] = a;
	root[pos] = rt;
	wh[pos] = res[a].size();
	res[a].push_back(pos);
	//pwh[pos] = posl.size();
	//posl.push_back(pos);
	if (rt != -1) {
		edc[rt]++;
		edc[pos] = 1;
	}
	else {
		edc[pos] = 0;
	}
}
inline int remdiff(int pos) {
	int ret = 1;
	int a = od[pos];
	od[pos] = -1;
	int g;
	for (int i = 0; i < ne[pos].size(); i++) {
		g = od[ne[pos][i]];
		if (g != -1) {
			if (mat[a][g] == 1) {
				if (mp[a][g] == 1) {
					ret -= 100;
				}
				if (updated[a][g] != upd) {
					updated[a][g] = upd;
					ud1.push_back(a);
					ud2.push_back(g);
					ud3.push_back(mp[a][g]);
				}
				mp[a][g]--;
				mp[g][a]--;
			}
		}
	}
	return ret;
}
inline void remove(int pos) {
	
	int a = od[pos];
	swap(res[a][wh[pos]], res[a].back());
	wh[res[a][wh[pos]]] = wh[pos];
	res[a].pop_back();
	wh[pos] = -1;
	/*swap(posl[pwh[pos]], posl.back());
	pwh[posl[pwh[pos]]] = pwh[pos];
	posl.pop_back();
	pwh[pos] = -1;*/
	if (root[pos] == -1) {
		if (edc[pos] == 1) {
			int k = -1;
			for (int i = 0; i < ne[pos].size(); i++) {
				if (root[ne[pos][i]] == pos) {
					k = ne[pos][i];
					break;
				}
			}
			/*if (k == -1) {
				cerr << "ERROR2" << endl;
			}*/
			root[k] = -1;
			edc[k]--;
		}
	}
	else {
		edc[root[pos]]--;
	}
	od[pos] = -1;
	edc[pos] = -1;
	root[pos] = -2;
}
void solveinit() {
	for (int i = 0; i < N; i++) {
		res[i].push_back(i);
	}
}
int SA() {
	mp.clear(); mp.resize(N, vector<int>(N, 0));
	updated.clear(); updated.resize(N, vector<int>(N, 0));
	//uval.clear(); uval.resize(N, vector<int>(N, 0));
	od.clear(); od.resize(V*V, -1);
	edc.clear(); edc.resize(V*V, 0);
	root.clear(); root.resize(V*V, -1);
	
	scp.clear(); scp.resize(N, 0);
	wh.clear(); wh.resize(V*V, -1);
	res.clear(); res.resize(N);
	upd = 0;
	//solveinit();
	vector<vector<int> > best;
	int bestscore = -1;
	double T;
	double T0 = 20;
	double ti;
	int t1, t2;
	int cnt = 0;
	int cnt2 = 0;
	int score = 5000 + N;
	int bf;
	double dtime = 0;
	int diff;
	int V2 = V*V;
	int kouho[10];
	int khsz = 0;
	{
		vector<int> list;
		int mn;
		int ss;
		for (int i = 0; i < V2; i++) {
			list.push_back(i);
		}
		for (int i = 0; i < N; i++) {
			mn = 100000000;
			for (int j = 0; j < list.size(); j++) {
				ss = abs((list[j] % V) - (V / 2)) + abs((list[j] / V) - (V / 2));
				if (mn > ss) {
					mn = ss;
					t1 = j;
				}
			}
			//t1 = rnd.nextInt(list.size());
			score += putdiff(i, list[t1]);
			put(i, list[t1], -1);
			swap(list[t1], list.back());
			list.pop_back();
		}
	}
	best = res;
	bestscore = score;
	cerr << score << endl;
	int posK;
	int posT;
	int val;
	double M = 0.0;
	
	//double Mdiff = 1e-6;
	//T = 25;
	T0 = 40;
	while (true) {
		if ((cnt & 0xFFF) == 0) {
			ti = timer.get();
			if (ti > TIMELIMIT_SA)break;
			T = (T0*(TIMELIMIT_SA - ti) / TIMELIMIT_SA) + 10;
			//T = 100 * pow(0.2, ti / TIMELIMIT_SA);
			//M = (ti / TIMELIMIT_SA) * 0.2;
			//M = 0.1 - M;
		}
	
#ifndef SUBMIT
		if (ti > dtime) {
			cerr << score << endl;
			dtime += 1;
		}
#endif
		//cerr << "ok" << endl;

		ud1.clear();
		ud2.clear();
		ud3.clear();
		//while (true)
		//{
			val = rnd.nextInt(N);
			posK = res[val][rnd.nextInt((int)res[val].size())];
			//if (edc[posK] <= 1)break;
		//}
		
		//posK = posl[rnd.nextInt(posl.size())];
		//val = od[posK];
		

	/*	if (edc[posK] == 1 && rnd.nextDouble() < M) {
		upd++;
			diff = remdiff(posK);
			od[posK] = val;
			if (diff >= 0 || diff > T*rnd.nextLog()) {
				cnt2++;
				score += diff;
				remove(posK);
			}
			else {
				undo();
			}

		}
		else*/ if (edc[posK] == 0 && rnd.nextInt(5) > 0) {
			t1 = ed[val][rnd.nextInt(ed[val].size())];
			t2 = res[t1][rnd.nextInt((int)res[t1].size())];
			
			khsz = 0;
			for (int i = 0; i < ne[t2].size(); i++) {
				if (od[ne[t2][i]] == -1 || edc[ne[t2][i]] <= 1) {
					kouho[khsz] = ne[t2][i];
					khsz++;
				}
			}
			if (khsz > 0) {
				posT = kouho[rnd.nextInt(khsz)];
				//posT = ne[t2][rnd.nextInt(ne[t2].size())];
				if (od[posT] == -1) {
					upd++;
					diff = remdiff(posK) + putdiff(val, posT);
					od[posT] = -1;
					od[posK] = val;
					if (diff >= 0 || diff > T*rnd.nextLog()) {
						cnt2++;
						score += diff;

						remove(posK);
						put(val, posT, -1);
						if (bestscore < score) {
							bestscore = score;
							best = res;
						}
					}
					else {
						undo();
					}
				}
				//else if (edc[posT] == 1 && rnd.nextDouble() < M) {
				else if (edc[posT] == 1) {
					if (od[posT] != od[posK]) {
						t1 = od[posT];
						upd++;
						diff = remdiff(posK) + remdiff(posT) + putdiff(val, posT);
						od[posK] = val;
						od[posT] = t1;
						if (diff >= 0 || diff > T*rnd.nextLog()) {
							cnt2++;
							score += diff;
							remove(posK);
							remove(posT);
							put(val, posT, -1);
							if (bestscore < score) {
								bestscore = score;
								best = res;
							}
						}
						else {
							undo();
						}
					}
				}
				else if (edc[posT] == 0) {
					if (od[posT] != od[posK]) {
						t1 = od[posT];
						upd++;
						diff = remdiff(posK) + remdiff(posT) + putdiff(val, posT) + putdiff(t1, posK);
						od[posK] = val;
						od[posT] = t1;
						if (diff >= 0 || diff > T*rnd.nextLog()) {
							/*if ((int)res[od[posT]].size() == 1) {
							cerr << "ERROR" << endl;
							}*/
							cnt2++;
							score += diff;

							remove(posK);
							remove(posT);
							put(val, posT, -1);
							put(t1, posK, -1);
							if (bestscore < score) {
								bestscore = score;
								best = res;
							}
						}
						else {
							undo();
						}
					}
				}
			}
		}
		else {
			khsz = 0;
			for (int i = 0; i < ne[posK].size(); i++) {
				if (od[ne[posK][i]] == -1 || edc[ne[posK][i]] <= 1) {
					kouho[khsz] = ne[posK][i];
					khsz++;
				}
			}
			if (khsz > 0) {
				posT = kouho[rnd.nextInt(khsz)];
			//posT = ne[posK][rnd.nextInt(ne[posK].size())];
				t1 = 0;
				for (int i = 0; i < ne[posT].size(); i++) {
					if (od[ne[posT][i]] == val)t1++;
				}
				if (t1 <= 1) {
					if (od[posT] == -1) {
						/*	t1 = 0;
							for (int i = 0; i < ne[posT].size(); i++) {
								if (od[ne[posT][i]] == val)t1++;
							}
							if (t1 <= 1) {*/
						upd++;
						diff = putdiff(val, posT);
						od[posT] = -1;
						if (diff >= 0 || diff > T*rnd.nextLog()) {
							score += diff;
							cnt2++;

							put(val, posT, posK);
							if (bestscore < score) {
								bestscore = score;
								best = res;
							}
						}
						else {
							undo();
						}
						//}
					}
					else if (edc[posT] == 1) {
						if (od[posT] != od[posK]) {
							t1 = od[posT];
							upd++;
							diff = remdiff(posT) + putdiff(val, posT);
							od[posT] = t1;
							if (diff >= 0 || diff > T*rnd.nextLog()) {
								score += diff;
								cnt2++;

								remove(posT);
								put(val, posT, posK);
								if (bestscore < score) {
									bestscore = score;
									best = res;
								}
							}
							else {
								undo();
							}
						}
					}
				}
			}

		}

		cnt++;

	}
	res = best;
	for (int i = 0; i < V2; i++) {
		od[i] = -1;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < res[i].size(); j++) {
			if (od[res[i][j]] != -1) {
				cerr << "ERROR" << endl;
			}
			od[res[i][j]] = i;
		}
	}
#ifndef  SUBMIT



	queue<int> qu;
	vector<int> v(V2, 0);
	vector<int> ch(N, 0);
	for (int i = 0; i < V2; i++) {
		if (v[i] == 0) {
			if (od[i] == -1) {
				v[i] = 1;
			}
			else {
				if (ch[od[i]] != 0) {
					cerr << "ERROR2" << endl;
				}
				qu.push(i);
				while (!qu.empty()) {
					t1 = qu.front();
					qu.pop();
					for (int j = 0; j < ne[t1].size(); j++) {
						if (od[ne[t1][j]] == od[i]) {
							if (v[ne[t1][j]] == 0) {
								v[ne[t1][j]] = 1;
								qu.push(ne[t1][j]);
							}
						}
					}
				}
				ch[od[i]] = 1;
			}
		}
	}

	int rs = getScore(od);
	score = rs * 100 + 5000;
	if (rs == E) {
		score += 100000;
	}
	for (int i = 0; i < N; i++) {
		score -= (int)res[i].size() - 1;
	}
	cerr << "cnt=" << cnt << endl;
	cerr << "cnt2=" << cnt2 << endl;
	cerr << "rawscore=" << score << endl;
#endif // ! SUBMIT
	res.clear();
	res.resize(N);
	for (int i = 0; i < V*V; i++) {
		if (od[i] != -1) {
			res[od[i]].push_back(i);
		}
	}
#ifndef SUBMIT
#ifndef BATCH
	ofstream ofs("od.csv");
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			ofs << od[i*V + j] << ",";
		}
		ofs << endl;
	}
#endif
#endif
	return score;
}
int solve() {
	rnd.init();
	input();
#ifndef SUBMIT
	timer.reset();
#endif
	setps();
	int score;

	cerr << N << " " << V << " " << E << endl;
	score = SA();

	cerr << "score" << score << endl;
#ifdef SUBMIT
	for (int i = 0; i < N; ++i) {
		cout << res[i].size();
		for (int j = 0; j < res[i].size(); j++) {
			cout << " " << (res[i][j] + 1);
		}
		cout << endl;
	}
#endif
	return score;
}
#ifdef SUBMIT
int main() {
	solve();
}
#else
#ifndef BATCH
int main() {
	for (int i = 0; i < 25; ++i) {
		input();
		init();
	}
	solve();
}
#else
int main() {
	int score;
	ofstream ofs("output.csv");
	for (int i = 0; i < 30; ++i) {
		init();
		score = solve();
		ofs << i << "," << N << "," << E << "," << score << endl;
	}
}
#endif
#endif

Submission Info

Judge Result