Submission #1867989

Source Code Expand

Copy
#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>
#include <bitset>
#include <string>
#include <iostream>
#include <array>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <sys/time.h>

#ifdef LOCAL
// #define MEASURE_TIME
// #define DEBUG
#else
#define NDEBUG
// #define DEBUG
#endif
#include <cassert>

using namespace std;
using  u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i64 = int64_t;
using  ll = int64_t;
using ull = uint64_t;
using  vi = vector<int>;
using vvi = vector<vi>;

namespace {

#ifdef LOCAL
const double CLOCK_PER_SEC = 2.2e9;
const ll TL = 29000;
#else
const double CLOCK_PER_SEC = 2.8e9;
const ll TL = 29900;
#endif

ll start_time; // msec

inline ll get_time() {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	ll result =  tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
	return result;
}

inline ll get_elapsed_msec() {
	return get_time() - start_time;
}

inline ull get_tsc() {
#ifdef __i386
  ull ret;
  __asm__ volatile ("rdtsc" : "=A" (ret));
  return ret;
#else
  ull high,low;
  __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
  return (high << 32) | low;
#endif
}

struct XorShift {
	uint32_t x,y,z,w;
	static const double TO_DOUBLE;

	XorShift() {
		x = 123456789;
		y = 362436069;
		z = 521288629;
		w = 88675123;
	}

	uint32_t nextUInt(uint32_t n) {
		uint32_t t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w % n;
	}

	uint32_t nextUInt() {
		uint32_t t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
	}

	double nextDouble() {
		return nextUInt() * TO_DOUBLE;
	}
};
const double XorShift::TO_DOUBLE = 1.0 / (1LL << 32);

struct Counter {
	vector<ull> cnt;

	void add(int i) {
		if (i >= cnt.size()) {
			cnt.resize(i+1);
		}
		++cnt[i];
	}

	void print() {
		cerr << "counter:[";
		for (int i = 0; i < cnt.size(); ++i) {
			cerr << cnt[i] << ", ";
			if (i % 10 == 9) cerr << endl;
		}
		cerr << "]" << endl;
	}
};

struct Timer {
	vector<ull> at;
	vector<ull> sum;

	void start(int i) {
		if (i >= at.size()) {
			at.resize(i+1);
			sum.resize(i+1);
		}
		at[i] = get_tsc();
	}

	void stop(int i) {
		sum[i] += (get_tsc() - at[i]);
	}

	void print() {
		cerr << "timer:[";
		for (int i = 0; i < at.size(); ++i) {
			cerr << (int)(sum[i] / CLOCK_PER_SEC * 1000) << ", ";
			if (i % 10 == 9) cerr << endl;
		}
		cerr << "]" << endl;
	}
};

}

#ifdef MEASURE_TIME
Timer timer;
Counter counter;
#define START_TIMER(i) (timer.start(i))
#define STOP_TIMER(i) (timer.stop(i))
#define PRINT_TIMER() (timer.print())
#define ADD_COUNTER(i) (counter.add(i))
#define PRINT_COUNTER() (counter.print())
#else
#define START_TIMER(i)
#define STOP_TIMER(i)
#define PRINT_TIMER()
#define ADD_COUNTER(i)
#define PRINT_COUNTER()
#endif

#ifdef DEBUG
#define debug(format, ...) fprintf(stderr, format, __VA_ARGS__)
#define debugStr(str) fprintf(stderr, str)
#define debugln() fprintf(stderr, "\n")
#else
#define debug(format, ...)
#define debugStr(str)
#define debugln()
#endif

template<class T>
inline T sq(T v) { return v * v; }

XorShift rnd;

//////// end of template ////////

struct has_edge {
	ull bits[8];

	has_edge() {
		fill(bits, bits + 8, 0ull);
	}

	bool operator[](int idx) const {
		return bits[idx >> 6] & (1ull << (idx & 63));
	}

	bool get(int idx) const {
		return bits[idx >> 6] & (1ull << (idx & 63));
	}

	void set(int idx) {
		bits[idx >> 6] |= (1ull << (idx & 63));
	}

	void clear(int idx) {
		bits[idx >> 6] &= ~(1ull << (idx & 63));
	}

	void clear() {
		fill(bits, bits + 8, 0ull);
	}
};

void swap(has_edge& e1, has_edge& e2) {
	swap(e1.bits[0], e2.bits[0]);
	swap(e1.bits[1], e2.bits[1]);
	swap(e1.bits[2], e2.bits[2]);
	swap(e1.bits[3], e2.bits[3]);
	swap(e1.bits[4], e2.bits[4]);
	swap(e1.bits[5], e2.bits[5]);
	swap(e1.bits[6], e2.bits[6]);
	swap(e1.bits[7], e2.bits[7]);
}

const int EMPTY_NODE = 0;
const double INF = 1e9;
const int DN[32] = {-65, -64, -63, -1, 1, 63, 64, 65, -65, -63, 63, 65, -65, -63, 63, 65, -65, -63, 63, 65, -65, -63, 63, 65, -65, -63, 63, 65, -65, -63, 63, 65};
int V, E, L, L2;
has_edge G[512];
vvi adj;
int edge_count[512][512];
int node_score[512];
int s_size[512];
int mapping[512], best_mapping[512], ans_mapping[512], rev_mapping[512];
int g_emb[64*64], best_g_emb[64*64], ans_g_emb[64*64];
int sur_bits[64*64];
int bfs_buf[64*64];
int bfs_idx = 1;
bool connected[1 << 8];
vi positions;
has_edge hes[512];

inline int get_pos(int r, int c) { return (r << 6) | c; }

void print_g_emb(const int* graph) {
#ifdef DEBUG
	for (int i = 1; i <= L; ++i) {
		for (int j = 1; j <= L; ++j) {
			debug("%3d ", graph[(i << 6) | j]);
		}
		debugln();
	}
#endif
}

void copy_g_emb(const int* from, int* to) {
	for (int i = 1; i <= L; ++i) {
		copy(from + (i << 6) + 1, from + (i << 6) + L + 1, to + (i << 6) + 1);
	}
}

void build_rev_mapping() {
	for (int i = 1; i <= V; ++i) {
		rev_mapping[mapping[i]] = i;
	}
}

void reset() {
	for (int i = 1; i <= L; ++i) {
		for (int j = 1; j <= L; ++j) {
			g_emb[get_pos(i, j)] = 0;
		}
		fill(bfs_buf + 64 * i, bfs_buf + 64 * i + L + 1, 0);
	}
	bfs_idx = 1;
	for (int i = 1; i <= V; ++i) {
		fill(edge_count[i], edge_count[i] + V + 1, 0);
		s_size[i] = 0;
		best_mapping[i] = mapping[i] = rev_mapping[i] = i;
	}
}

void create_initial_sparse() {
	int len = min(L, (int)ceil(sqrt(2 * V)));
	int margin = (L - len) / 2;
	vi pos;
	for (int i = 0; i < len; ++i) {
		for (int j = 0; j < len; ++j) {
			pos.push_back(get_pos(i + margin + 1, j + margin + 1));
		}
	}
	random_shuffle(pos.begin(), pos.end());
	for (int i = 0; i < V; ++i) {
		g_emb[pos[i]] = i + 1;
	}
	// print_g_emb(g_emb);
}

void create_initial_complete() {
	int len = V > L ? L : V;
	int margin = (L - len) / 2;
	vvi pos((len + 1) / 2);
	for (int i = 0; i + 1 < len; i += 2) {
		vi last;
		for (int j = 0; j < len; ++j) {
			int x = i - j;
			if (x < 0) x = -x - 1;
			pos[i / 2].push_back(get_pos(margin + j + 1, margin + x + 1));
			x = i + 1 + j;
			if (x >= len) x = len - 1 - (x - len);
			last.push_back(get_pos(margin + j + 1, margin + x + 1));
		}
		pos[i / 2].insert(pos[i / 2].end(), last.rbegin(), last.rend());
	}
	if (len % 2 == 1) {
		for (int i = 0; i < len; ++i) {
			pos.back().push_back(get_pos(margin + i + 1, margin + len - 1 - i + 1));
		}
	}
	vi nodes = vi(V);
	for (int i = 0; i < V; ++i) {
		nodes[i] = i + 1;
	}
	random_shuffle(nodes.begin(), nodes.end());
	vi counts(pos.size());
	for (int i = 0; i < pos.size(); ++i) {
		counts[i] = 1;
	}
	for (int i = pos.size(); i < V; ++i) {
		int mi = 0;
		double mv = 0;
		for (int j = 0; j < pos.size(); ++j) {
			if (1.0 * pos[j].size() / counts[j] > mv) {
				mi = j;
				mv = 1.0 * pos[j].size() / counts[j];
			}
		}
		counts[mi]++;
	}
	int ni = 0;
	for (int i = 0; i < pos.size(); ++i) {
		int gap = (V <= L || (len % 2 == 1 && i == pos.size() - 1)) ? 0 : i;
		for (int j = 0; j < counts[i]; ++j) {
			for (int k = pos[i].size() * j / counts[i]; k < pos[i].size() * (j + 1) / counts[i]; ++k) {
				g_emb[pos[i][(k + gap) % pos[i].size()]] = nodes[ni];
			}
			++ni;
		}
	}
	// print_g_emb(g_emb);
}

int get_sur(int p) {
	int ret = 0;
	for (int i = 0; i < 8; ++i) {
		if (g_emb[p + DN[i]] == g_emb[p]) ret |= 1 << i;
	}
	return ret;
}

int bfs_q[256];
template<bool first>
bool do_bfs(int p, int v, int signature) {
	int qs = 1;
	bfs_q[0] = p;
	bfs_buf[p & 0xFFFF] = signature;
	int qi = 0;
	for (int i = 0; i < 5; ++i) {
		for (int sz = qs; qi < sz; ++qi) {
			int pos = bfs_q[qi] & 0xFFFF;
			int sur = bfs_q[qi] >> 16;
			while (sur > 0) {
				int ni = __builtin_ctz(sur);
				if (bfs_buf[pos + DN[ni]] != signature) {
					if (!first && bfs_buf[pos + DN[ni]] >= bfs_idx) return true;
					bfs_buf[pos + DN[ni]] = signature;
					int bits = sur_bits[pos + DN[ni]] - (1 << (7 - ni));
					bfs_q[qs++] = (pos + DN[ni]) | (bits << 16);
				}
				sur &= sur - 1;
			}
		}
	}
	if (first) return qi == qs;
	return false;
}

bool is_sur_connected(int p, int v) {
	START_TIMER(3);
	int sur = sur_bits[p];
	if (connected[sur]) {
		ADD_COUNTER(0);
		return true;
	}
	if (edge_count[v][v] == (s_size[v] - 1) * 2) return false; // is tree?
	if ((sur & ((1 << 0) | (1 << 1) | (1 << 2))) == ((1 << 0) | (1 << 2)) && g_emb[p - 128] == v) {
		sur |= 1 << 1;
	}
	if ((sur & ((1 << 2) | (1 << 4) | (1 << 7))) == ((1 << 2) | (1 << 7)) && g_emb[p + 2] == v) {
		sur |= 1 << 4;
	}
	if ((sur & ((1 << 7) | (1 << 6) | (1 << 5))) == ((1 << 7) | (1 << 5)) && g_emb[p + 128] == v) {
		sur |= 1 << 6;
	}
	if ((sur & ((1 << 5) | (1 << 3) | (1 << 0))) == ((1 << 5) | (1 << 0)) && g_emb[p - 2] == v) {
		sur |= 1 << 3;
	}
	if (connected[sur]) {
		ADD_COUNTER(1);
		return true;
	}
	sur = sur_bits[p];
	int i = __builtin_ctz(sur);
	bfs_buf[p] = bfs_idx + i;
	int bits = sur_bits[p + DN[i]] - (1 << (7 - i));
	bool result = do_bfs<true>((p + DN[i]) | (bits << 16), v, bfs_idx + i);
	sur &= sur - 1;
	if (result) {
		do {
			int i = __builtin_ctz(sur);
			if (bfs_buf[p + DN[i]] < bfs_idx) {
				result = false;
				break;
			}
			sur &= sur - 1;
		} while (sur);
	} else {
		do {
			result = true;
			int i = __builtin_ctz(sur);
			if (bfs_buf[p + DN[i]] < bfs_idx) {
				bfs_buf[p] = bfs_idx + i;
				int bits = sur_bits[p + DN[i]] - (1 << (7 - i));
				if (!do_bfs<false>((p + DN[i]) | (bits << 16), v, bfs_idx + i)) {
					result = false;
					break;
				}
			}
			sur &= sur - 1;
		} while (sur);
	}
	bfs_idx += 8;
	STOP_TIMER(3);
	ADD_COUNTER(result ? 2 : 3);
	return result;
}

int add(int p, int new_val) {
	int ret = 0;
	const int rnv = mapping[new_val];
	if (edge_count[new_val][g_emb[p-65]] == 0) {
		if (G[rnv][mapping[g_emb[p-65]]]) {
			++ret;
			node_score[new_val]++;
			node_score[g_emb[p-65]]++;
		}
		hes[rnv].set(mapping[g_emb[p-65]]);
		hes[mapping[g_emb[p-65]]].set(rnv);
	}
	edge_count[new_val][g_emb[p-65]]++;
	if (edge_count[new_val][g_emb[p-64]] == 0) {
		if (G[rnv][mapping[g_emb[p-64]]]) {
			++ret;
			node_score[new_val]++;
			node_score[g_emb[p-64]]++;
		}
		hes[rnv].set(mapping[g_emb[p-64]]);
		hes[mapping[g_emb[p-64]]].set(rnv);
	}
	edge_count[new_val][g_emb[p-64]]++;
	if (edge_count[new_val][g_emb[p-63]] == 0) {
		if (G[rnv][mapping[g_emb[p-63]]]) {
			++ret;
			node_score[new_val]++;
			node_score[g_emb[p-63]]++;
		}
		hes[rnv].set(mapping[g_emb[p-63]]);
		hes[mapping[g_emb[p-63]]].set(rnv);
	}
	edge_count[new_val][g_emb[p-63]]++;
	if (edge_count[new_val][g_emb[p-1]] == 0) {
		if (G[rnv][mapping[g_emb[p-1]]]) {
			++ret;
			node_score[new_val]++;
			node_score[g_emb[p-1]]++;
		}
		hes[rnv].set(mapping[g_emb[p-1]]);
		hes[mapping[g_emb[p-1]]].set(rnv);
	}
	edge_count[new_val][g_emb[p-1]]++;
	if (edge_count[new_val][g_emb[p+1]] == 0) {
		if (G[rnv][mapping[g_emb[p+1]]]) {
			++ret;
			node_score[new_val]++;
			node_score[g_emb[p+1]]++;
		}
		hes[rnv].set(mapping[g_emb[p+1]]);
		hes[mapping[g_emb[p+1]]].set(rnv);
	}
	edge_count[new_val][g_emb[p+1]]++;
	if (edge_count[new_val][g_emb[p+63]] == 0) {
		if (G[rnv][mapping[g_emb[p+63]]]) {
			++ret;
			node_score[new_val]++;
			node_score[g_emb[p+63]]++;
		}
		hes[rnv].set(mapping[g_emb[p+63]]);
		hes[mapping[g_emb[p+63]]].set(rnv);
	}
	edge_count[new_val][g_emb[p+63]]++;
	if (edge_count[new_val][g_emb[p+64]] == 0) {
		if (G[rnv][mapping[g_emb[p+64]]]) {
			++ret;
			node_score[new_val]++;
			node_score[g_emb[p+64]]++;
		}
		hes[rnv].set(mapping[g_emb[p+64]]);
		hes[mapping[g_emb[p+64]]].set(rnv);
	}
	edge_count[new_val][g_emb[p+64]]++;
	if (edge_count[new_val][g_emb[p+65]] == 0) {
		if (G[rnv][mapping[g_emb[p+65]]]) {
			++ret;
			node_score[new_val]++;
			node_score[g_emb[p+65]]++;
		}
		hes[rnv].set(mapping[g_emb[p+65]]);
		hes[mapping[g_emb[p+65]]].set(rnv);
	}
	edge_count[new_val][g_emb[p+65]]++;
	edge_count[g_emb[p-65]][new_val]++;
	edge_count[g_emb[p-64]][new_val]++;
	edge_count[g_emb[p-63]][new_val]++;
	edge_count[g_emb[p-1]][new_val]++;
	edge_count[g_emb[p+1]][new_val]++;
	edge_count[g_emb[p+63]][new_val]++;
	edge_count[g_emb[p+64]][new_val]++;
	edge_count[g_emb[p+65]][new_val]++;
	return ret;
}

int remove(int p, int old_val) {
	int ret = 0;
	const int rov = mapping[old_val];
	edge_count[old_val][g_emb[p-65]]--;
	if (edge_count[old_val][g_emb[p-65]] == 0) {
		if (G[rov][mapping[g_emb[p-65]]]) {
			--ret;
			node_score[old_val]--;
			node_score[g_emb[p-65]]--;
		}
		hes[rov].clear(mapping[g_emb[p-65]]);
		hes[mapping[g_emb[p-65]]].clear(rov);
	}
	edge_count[old_val][g_emb[p-64]]--;
	if (edge_count[old_val][g_emb[p-64]] == 0) {
		if (G[rov][mapping[g_emb[p-64]]]) {
			--ret;
			node_score[old_val]--;
			node_score[g_emb[p-64]]--;
		}
		hes[rov].clear(mapping[g_emb[p-64]]);
		hes[mapping[g_emb[p-64]]].clear(rov);
	}
	edge_count[old_val][g_emb[p-63]]--;
	if (edge_count[old_val][g_emb[p-63]] == 0) {
		if (G[rov][mapping[g_emb[p-63]]]) {
			--ret;
			node_score[old_val]--;
			node_score[g_emb[p-63]]--;
		}
		hes[rov].clear(mapping[g_emb[p-63]]);
		hes[mapping[g_emb[p-63]]].clear(rov);
	}
	edge_count[old_val][g_emb[p-1]]--;
	if (edge_count[old_val][g_emb[p-1]] == 0) {
		if (G[rov][mapping[g_emb[p-1]]]) {
			--ret;
			node_score[old_val]--;
			node_score[g_emb[p-1]]--;
		}
		hes[rov].clear(mapping[g_emb[p-1]]);
		hes[mapping[g_emb[p-1]]].clear(rov);
	}
	edge_count[old_val][g_emb[p+1]]--;
	if (edge_count[old_val][g_emb[p+1]] == 0) {
		if (G[rov][mapping[g_emb[p+1]]]) {
			--ret;
			node_score[old_val]--;
			node_score[g_emb[p+1]]--;
		}
		hes[rov].clear(mapping[g_emb[p+1]]);
		hes[mapping[g_emb[p+1]]].clear(rov);
	}
	edge_count[old_val][g_emb[p+63]]--;
	if (edge_count[old_val][g_emb[p+63]] == 0) {
		if (G[rov][mapping[g_emb[p+63]]]) {
			--ret;
			node_score[old_val]--;
			node_score[g_emb[p+63]]--;
		}
		hes[rov].clear(mapping[g_emb[p+63]]);
		hes[mapping[g_emb[p+63]]].clear(rov);
	}
	edge_count[old_val][g_emb[p+64]]--;
	if (edge_count[old_val][g_emb[p+64]] == 0) {
		if (G[rov][mapping[g_emb[p+64]]]) {
			--ret;
			node_score[old_val]--;
			node_score[g_emb[p+64]]--;
		}
		hes[rov].clear(mapping[g_emb[p+64]]);
		hes[mapping[g_emb[p+64]]].clear(rov);
	}
	edge_count[old_val][g_emb[p+65]]--;
	if (edge_count[old_val][g_emb[p+65]] == 0) {
		if (G[rov][mapping[g_emb[p+65]]]) {
			--ret;
			node_score[old_val]--;
			node_score[g_emb[p+65]]--;
		}
		hes[rov].clear(mapping[g_emb[p+65]]);
		hes[mapping[g_emb[p+65]]].clear(rov);
	}
	edge_count[g_emb[p-65]][old_val]--;
	edge_count[g_emb[p-64]][old_val]--;
	edge_count[g_emb[p-63]][old_val]--;
	edge_count[g_emb[p-1]][old_val]--;
	edge_count[g_emb[p+1]][old_val]--;
	edge_count[g_emb[p+63]][old_val]--;
	edge_count[g_emb[p+64]][old_val]--;
	edge_count[g_emb[p+65]][old_val]--;
	return ret;
}

int calc_score() {
	int score = 5000;
	vvi ec(V + 1, vi(V + 1));
	for (int i = 1; i <= L; ++i) {
		for (int j = 1; j <= L; ++j) {
			const int p = get_pos(i, j);
			if (ec[g_emb[p]][g_emb[p+1]] == 0 && G[mapping[g_emb[p]]][mapping[g_emb[p+1]]]) score += 100;
			ec[g_emb[p]][g_emb[p+1]]++;
			ec[g_emb[p+1]][g_emb[p]]++;
			if (ec[g_emb[p]][g_emb[p+63]] == 0 && G[mapping[g_emb[p]]][mapping[g_emb[p+63]]]) score += 100;
			ec[g_emb[p]][g_emb[p+63]]++;
			ec[g_emb[p+63]][g_emb[p]]++;
			if (ec[g_emb[p]][g_emb[p+64]] == 0 && G[mapping[g_emb[p]]][mapping[g_emb[p+64]]]) score += 100;
			ec[g_emb[p]][g_emb[p+64]]++;
			ec[g_emb[p+64]][g_emb[p]]++;
			if (ec[g_emb[p]][g_emb[p+65]] == 0 && G[mapping[g_emb[p]]][mapping[g_emb[p+65]]]) score += 100;
			ec[g_emb[p]][g_emb[p+65]]++;
			ec[g_emb[p+65]][g_emb[p]]++;
		}
	}
	for (int i = 1; i <= V; ++i) {
		score -= s_size[i] - 1;
	}
	return score;
}

int update_interval;
double cooler;
double cooler_mul;
inline bool accept(int diff) {
	if (diff >= 0) return true;
	const double mul = diff * cooler;
	if (mul < -6) return false;
	return rnd.nextDouble() < exp(mul);
}

// g_emb[p2] -> EMPTY_NODE
bool shrink(int& score, int p1, int p2) {
	const int v = g_emb[p1];
	int diff = remove(p2, v) * 100 + 1;
	if (accept(diff)) {
		score += diff;
		s_size[v]--;
		g_emb[p2] = EMPTY_NODE;
		int bits = sur_bits[p2];
		while (bits) {
			int si = __builtin_ctz(bits);
			sur_bits[p2 + DN[si]] -= 1 << (7 - si);
			bits &= bits - 1;
		}
		return true;
	} else {
		add(p2, g_emb[p2]);
		return false;
	}
}

// g_emb[p2](EMPTY_NODE) -> v1
bool expand(int& score, int p1, int p2) {
	const int v1 = g_emb[p1];
	int diff = add(p2, v1) * 100 - 1;
	if (accept(diff)) {
		score += diff;
		s_size[v1]++;
		g_emb[p2] = v1;
		sur_bits[p2] = 0;
		if (g_emb[p2 - 65] == v1) {
			sur_bits[p2 - 65] |= 1 << 7;
			sur_bits[p2] |= 1 << 0;
		}
		if (g_emb[p2 - 64] == v1) {
			sur_bits[p2 - 64] |= 1 << 6;
			sur_bits[p2] |= 1 << 1;
		}
		if (g_emb[p2 - 63] == v1) {
			sur_bits[p2 - 63] |= 1 << 5;
			sur_bits[p2] |= 1 << 2;
		}
		if (g_emb[p2 -  1] == v1) {
			sur_bits[p2 -  1] |= 1 << 4;
			sur_bits[p2] |= 1 << 3;
		}
		if (g_emb[p2 +  1] == v1) {
			sur_bits[p2 +  1] |= 1 << 3;
			sur_bits[p2] |= 1 << 4;
		}
		if (g_emb[p2 + 63] == v1) {
			sur_bits[p2 + 63] |= 1 << 2;
			sur_bits[p2] |= 1 << 5;
		}
		if (g_emb[p2 + 64] == v1) {
			sur_bits[p2 + 64] |= 1 << 1;
			sur_bits[p2] |= 1 << 6;
		}
		if (g_emb[p2 + 65] == v1) {
			sur_bits[p2 + 65] |= 1 << 0;
			sur_bits[p2] |= 1 << 7;
		}
		return true;
	} else {
		remove(p2, v1);
		return false;
	}
}

// g_emb[p2](not EMPTY_NODE) -> v1
bool invade(int& score, int p1, int p2) {
	const int v1 = g_emb[p1];
	const int v2 = g_emb[p2];
	int diff = remove(p2, v2);
	diff += add(p2, v1);
	diff *= 100;
	if (accept(diff)) {
		score += diff;
		s_size[v1]++;
		s_size[v2]--;
		g_emb[p2] = v1;
		sur_bits[p2] = 0;
		if (g_emb[p2 - 65] == v2) {
			sur_bits[p2 - 65] -= 1 << 7;
		} else if (g_emb[p2 - 65] == v1) {
			sur_bits[p2 - 65] |= 1 << 7;
			sur_bits[p2] |= 1 << 0;
		}
		if (g_emb[p2 - 64] == v2) {
			sur_bits[p2 - 64] -= 1 << 6;
		} else if (g_emb[p2 - 64] == v1) {
			sur_bits[p2 - 64] |= 1 << 6;
			sur_bits[p2] |= 1 << 1;
		}
		if (g_emb[p2 - 63] == v2) {
			sur_bits[p2 - 63] -= 1 << 5;
		} else if (g_emb[p2 - 63] == v1) {
			sur_bits[p2 - 63] |= 1 << 5;
			sur_bits[p2] |= 1 << 2;
		}
		if (g_emb[p2 -  1] == v2) {
			sur_bits[p2 -  1] -= 1 << 4;
		} else if (g_emb[p2 - 1] == v1) {
			sur_bits[p2 - 1] |= 1 << 4;
			sur_bits[p2] |= 1 << 3;
		}
		if (g_emb[p2 +  1] == v2) {
			sur_bits[p2 +  1] -= 1 << 3;
		} else if (g_emb[p2 + 1] == v1) {
			sur_bits[p2 + 1] |= 1 << 3;
			sur_bits[p2] |= 1 << 4;
		}
		if (g_emb[p2 + 63] == v2) {
			sur_bits[p2 + 63] -= 1 << 2;
		} else if (g_emb[p2 + 63] == v1) {
			sur_bits[p2 + 63] |= 1 << 2;
			sur_bits[p2] |= 1 << 5;
		}
		if (g_emb[p2 + 64] == v2) {
			sur_bits[p2 + 64] -= 1 << 1;
		} else if (g_emb[p2 + 64] == v1) {
			sur_bits[p2 + 64] |= 1 << 1;
			sur_bits[p2] |= 1 << 6;
		}
		if (g_emb[p2 + 65] == v2) {
			sur_bits[p2 + 65] -= 1 << 0;
		} else if (g_emb[p2 + 65] == v1) {
			sur_bits[p2 + 65] |= 1 << 0;
			sur_bits[p2] |= 1 << 7;
		}
		ADD_COUNTER(10);
		return true;
	} else {
		remove(p2, v1);
		add(p2, v2);
		ADD_COUNTER(11);
		return false;
	}
}

bool swap_node(int& score, int v1, int v2) {
	START_TIMER(2);
	int add1 = 0;
	int add2 = 0;
	const int r1 = mapping[v1];
	const int r2 = mapping[v2];
	hes[r1].clear(r1);
	hes[r2].clear(r2);
	if (G[r1][r2] && hes[r1][r2]) {
		++add1;
		++add2;
	}
	for (int i = 0; i * 64 <= V; ++i) {
		ull bits = G[r1].bits[i] & hes[r2].bits[i];
		add1 += __builtin_popcountll(bits);
		bits = G[r2].bits[i] & hes[r1].bits[i];
		add2 += __builtin_popcountll(bits);
	}
	int diff = (add1 + add2 - node_score[v1] - node_score[v2]) * 100;
	STOP_TIMER(2);
	if (accept(diff)) {
		START_TIMER(10);
		score += diff;
		ull bits[8];
		for (int i = 0; i * 64 <= V; ++i) {
			bits[i] = hes[r1].bits[i] ^ hes[r2].bits[i];
		}
		for (int i = 0; i * 64 <= V; ++i) {
			while (bits[i]) {
				int idx = i * 64 + __builtin_ctzll(bits[i]);
				if (hes[idx][r1]) {
					hes[idx].clear(r1);
					hes[idx].set(r2);
					if (G[idx][r1]) node_score[rev_mapping[idx]]--;
					if (G[idx][r2]) node_score[rev_mapping[idx]]++;
				} else {
					hes[idx].set(r1);
					hes[idx].clear(r2);
					if (G[idx][r2]) node_score[rev_mapping[idx]]--;
					if (G[idx][r1]) node_score[rev_mapping[idx]]++;
				}
				bits[i] &= bits[i] - 1;
			}
		}
		swap(mapping[v1], mapping[v2]);
		swap(rev_mapping[r1], rev_mapping[r2]);
		swap(hes[r1], hes[r2]);
		node_score[v2] = add1;
		node_score[v1] = add2;
		STOP_TIMER(10);
		return true;
	}
	return false;
}

int simulated_annealing(ll time_limit, double init_cooler, double init_cooler_mul) {
	cooler = init_cooler;
	cooler_mul = init_cooler_mul;
	auto init = [](){
		for (int i = 1; i <= V; ++i) {
			fill(edge_count[i], edge_count[i] + V + 1, 0);
			s_size[i] = 0;
			node_score[i] = 0;
			hes[i].clear();
		}
		int s = 5000;
		for (int i = 1; i <= L; ++i) {
			for (int j = 1; j <= L; ++j) {
				const int p = get_pos(i, j);
				s_size[g_emb[p]]++;
				if (edge_count[g_emb[p]][g_emb[p+1]] == 0) {
					if (G[mapping[g_emb[p]]][mapping[g_emb[p+1]]]) {
						s += 100;
						node_score[g_emb[p]]++;
						node_score[g_emb[p+1]]++;
					}
					hes[mapping[g_emb[p]]].set(mapping[g_emb[p+1]]);
					hes[mapping[g_emb[p+1]]].set(mapping[g_emb[p]]);
				}
				edge_count[g_emb[p]][g_emb[p+1]]++;
				edge_count[g_emb[p+1]][g_emb[p]]++;
				if (edge_count[g_emb[p]][g_emb[p+63]] == 0) {
					if (G[mapping[g_emb[p]]][mapping[g_emb[p+63]]]) {
						s += 100;
						node_score[g_emb[p]]++;
						node_score[g_emb[p+63]]++;
					}
					hes[mapping[g_emb[p]]].set(mapping[g_emb[p+63]]);
					hes[mapping[g_emb[p+63]]].set(mapping[g_emb[p]]);
				}
				edge_count[g_emb[p]][g_emb[p+63]]++;
				edge_count[g_emb[p+63]][g_emb[p]]++;
				if (edge_count[g_emb[p]][g_emb[p+64]] == 0) {
					if (G[mapping[g_emb[p]]][mapping[g_emb[p+64]]]) {
						s += 100;
						node_score[g_emb[p]]++;
						node_score[g_emb[p+64]]++;
					}
					hes[mapping[g_emb[p]]].set(mapping[g_emb[p+64]]);
					hes[mapping[g_emb[p+64]]].set(mapping[g_emb[p]]);
				}
				edge_count[g_emb[p]][g_emb[p+64]]++;
				edge_count[g_emb[p+64]][g_emb[p]]++;
				if (edge_count[g_emb[p]][g_emb[p+65]] == 0) {
					if (G[mapping[g_emb[p]]][mapping[g_emb[p+65]]]) {
						s += 100;
						node_score[g_emb[p]]++;
						node_score[g_emb[p+65]]++;
					}
					hes[mapping[g_emb[p]]].set(mapping[g_emb[p+65]]);
					hes[mapping[g_emb[p+65]]].set(mapping[g_emb[p]]);
				}
				edge_count[g_emb[p]][g_emb[p+65]]++;
				edge_count[g_emb[p+65]][g_emb[p]]++;
				best_g_emb[p] = g_emb[p];
				if (g_emb[p] != EMPTY_NODE) sur_bits[p] = get_sur(p);
			}
		}
		for (int i = 1; i <= V; ++i) {
			s -= s_size[i] - 1;
		}
		return s;
	};
	int score = init();
	int best_score = score;
	debug("init score:%d\n", score);
	int update_count = 0;
	int last_best_turn = 0;
	int swap_mask = 1;
	for (int turn = 0; ; ++turn) {
		// debug("turn:%d\n", turn);
		if ((turn & 0x3FFF) == 0) {
			const ll elapsed = get_elapsed_msec();
			if (elapsed > time_limit) {
				int node_count = 0;
				for (int i = 1; i <= L; ++i) {
					for (int j = 1; j <= L; ++j) {
						if (best_g_emb[get_pos(i, j)] != EMPTY_NODE) node_count++;
					}
				}
				if (E * 100 + 5000 - (node_count - V) == best_score) best_score += 100000;
				debug("turn:%d score:%d\n", turn, best_score);
				break;
			} else if (elapsed > time_limit - 50 && cooler < INF) {
				update_count = 0;
				swap_mask = 1;
				cooler = INF;
				copy_g_emb(best_g_emb, g_emb);
				copy(best_mapping, best_mapping + V + 1, mapping);
				build_rev_mapping();
				score = init();
				last_best_turn = turn;
				debug("turn:%d best:%d score:%d cooler:%f\n", turn, best_score, score, cooler);
			} else if (update_count >= update_interval) {
				if (cooler < INF) {
					update_count = 0;
					cooler *= cooler_mul;
					if (cooler > 2) {
						time_limit = elapsed + 50;
					}
					debug("turn:%d best:%d score:%d cooler:%f\n", turn, best_score, score, cooler);
				}
			} else if (turn > last_best_turn + 5000000) {
				debug("revert to best:%d\n", turn);
				copy_g_emb(best_g_emb, g_emb);
				copy(best_mapping, best_mapping + V + 1, mapping);
				build_rev_mapping();
				score = init();
				last_best_turn = turn;
				if (cooler > init_cooler * 50) cooler = init_cooler * 50;
			}
		}
		bool updated = false;
		if (turn & swap_mask) {
			START_TIMER(6);
			int v1 = rnd.nextUInt() % V;
			int v2 = rnd.nextUInt() % (V - 1);
			if (v2 >= v1) v2++;
			STOP_TIMER(6);
			updated = swap_node(score, v1 + 1, v2 + 1);
			// debug("swap %d %d\n", v1, v2);
		} else {
			START_TIMER(4);
			int p1 = positions[rnd.nextUInt() & (positions.size() - 1)];
			int v1 = g_emb[p1];
			while (v1 == EMPTY_NODE) {
				p1 = positions[rnd.nextUInt() & (positions.size() - 1)];
				v1 = g_emb[p1];
			}
			int p2;
			do {
				int dir = rnd.nextUInt() & 31;
				p2 = p1 + DN[dir];
			} while (p2 < 64 || ((L + 1) << 6) < p2 || (p2 & 0x3F) == 0 || (p2 & 0x3F) == L + 1);
			const int v2 = g_emb[p2];
			STOP_TIMER(4);
			if (v1 == v2) {
				if (!is_sur_connected(p2, v2)) {
					continue;
				}
				START_TIMER(7);
				updated = shrink(score, p1, p2);
				STOP_TIMER(7);
			// debug("shrink %x %x\n", p1, p2);
			} else if (v2 == EMPTY_NODE) {
				START_TIMER(8);
				updated = expand(score, p1, p2);
				STOP_TIMER(8);
				// debug("expand %x %x\n", p1, p2);
			} else {
				if (s_size[v2] == 1 || !is_sur_connected(p2, v2)) {
					int vi = rnd.nextUInt() % adj[mapping[v1]].size();
					int v3 = rev_mapping[adj[mapping[v1]][vi]];
					if (v3 == v2) {
						vi++;
						if (vi == adj[mapping[v1]].size()) vi = 0;
						v3 = rev_mapping[adj[mapping[v1]][vi]];
					}
					updated = swap_node(score, v3, v2);
					// debug("swap2 %x %x\n", p1, p2);
				} else {
					START_TIMER(9);
					updated = invade(score, p1, p2);
					STOP_TIMER(9);
					// debug("invade %x %x\n", p1, p2);
				}
			}
		}
		ADD_COUNTER(5);
		if (updated) {
			START_TIMER(1);
			ADD_COUNTER(6);
			++update_count;
			if (score > best_score) {
				best_score = score;
				last_best_turn = turn;
				copy_g_emb(g_emb, best_g_emb);
				copy(mapping, mapping + V + 1, best_mapping);
				// debug("turn:%d best_score:%d\n", turn, score);
			}
			STOP_TIMER(1);
		}
	}
	return best_score;
}

bool check_connected(int bits) {
	int v[8];
	for (int i = 0; i < 8; ++i) {
		v[i] = bits & (1 << i);
	}
	for (int i = 0; i < 8; ++i) {
		if (v[0] & (1 << 0)) {
			v[1] |= v[0];
			v[3] |= v[0];
		}
		if (v[1] & (1 << 1)) {
			v[0] |= v[1];
			v[2] |= v[1];
			v[3] |= v[1];
			v[4] |= v[1];
		}
		if (v[2] & (1 << 2)) {
			v[1] |= v[2];
			v[4] |= v[2];
		}
		if (v[3] & (1 << 3)) {
			v[0] |= v[3];
			v[1] |= v[3];
			v[5] |= v[3];
			v[6] |= v[3];
		}
		if (v[4] & (1 << 4)) {
			v[1] |= v[4];
			v[2] |= v[4];
			v[6] |= v[4];
			v[7] |= v[4];
		}
		if (v[5] & (1 << 5)) {
			v[3] |= v[5];
			v[6] |= v[5];
		}
		if (v[6] & (1 << 6)) {
			v[3] |= v[6];
			v[4] |= v[6];
			v[5] |= v[6];
			v[7] |= v[6];
		}
		if (v[7] & (1 << 7)) {
			v[4] |= v[7];
			v[6] |= v[7];
		}
	}
	for (int i = 0; i < 8; ++i) {
		if ((bits & (1 << i)) && v[i] != bits) return false;
	}
	return true;
}

int prev_dir[64*64];
has_edge g_back[512];
int finalize(ll timelimit) {
	vvi port(V+1);
	for (int i = 1; i <= V; ++i) {
		for (int j = 0; j * 64 <= V; ++j) {
			g_back[i].bits[j] = G[i].bits[j];
		}
	}
	for (int i = 1; i <= L; ++i) {
		for (int j = 1; j <= L; ++j) {
			const int p = get_pos(i, j);
			const int v = best_g_emb[p];
			if (v == EMPTY_NODE) {
				for (int k = 0; k < 8; ++k) {
					const int nv = best_g_emb[p+DN[k]];
					if (nv != EMPTY_NODE) {
						port[nv].push_back(p);
					}
				}
				continue;
			}
			if (best_g_emb[p+1] != EMPTY_NODE) {
				G[best_mapping[v]].clear(best_mapping[best_g_emb[p+1]]);
				G[best_mapping[best_g_emb[p+1]]].clear(best_mapping[v]);
			}
			if (best_g_emb[p+63] != EMPTY_NODE) {
				G[best_mapping[v]].clear(best_mapping[best_g_emb[p+63]]);
				G[best_mapping[best_g_emb[p+63]]].clear(best_mapping[v]);
			}
			if (best_g_emb[p+64] != EMPTY_NODE) {
				G[best_mapping[v]].clear(best_mapping[best_g_emb[p+64]]);
				G[best_mapping[best_g_emb[p+64]]].clear(best_mapping[v]);
			}
			if (best_g_emb[p+65] != EMPTY_NODE) {
				G[best_mapping[v]].clear(best_mapping[best_g_emb[p+65]]);
				G[best_mapping[best_g_emb[p+65]]].clear(best_mapping[v]);
			}
		}
	}
	for (int i = 0; i <= L + 1; ++i) {
		bfs_buf[get_pos(0, i)] = 1 << 30;
		bfs_buf[get_pos(L + 1, i)] = 1 << 30;
		bfs_buf[get_pos(i, 0)] = 1 << 30;
		bfs_buf[get_pos(i, L + 1)] = 1 << 30;
	}
	vi ord;
	for (int i = 1; i <= V; ++i) {
		int sum = 0;
		for (int j = 0; j * 64 <= V; ++j) {
			sum += __builtin_popcountll(G[best_mapping[i]].bits[j]);
		}
		if (sum > 0 && !port[i].empty()) {
			ord.push_back((sum << 16) | i);
		}
	}
	sort(ord.begin(), ord.end());
	vi q, goal;
	int score_diff = 0;
	for (int i = (int)ord.size() - 1; i >= 0; --i) {
		if (get_elapsed_msec() >= timelimit) {
			debug("final:%d %d\n", i, (int)ord.size());
			break;
		}
		const int v = ord[i] & 0xFFFF;
		q.clear();
		goal.clear();
		for (int p : port[v]) {
			if (best_g_emb[p] != EMPTY_NODE) continue;
			q.push_back(p);
			prev_dir[p] = -1;
		}
		for (int qi = 0; qi < q.size(); ++qi) {
			int cp = q[qi];
			for (int dir = 0; dir < 8; ++dir) {
				int np = cp + DN[dir];
				if (bfs_buf[np] >= bfs_idx) continue;
				int nv = best_g_emb[np];
				if (nv == EMPTY_NODE) {
					q.push_back(np);
					prev_dir[np] = 7 - dir;
					bfs_buf[np] = bfs_idx;
				} else if (G[best_mapping[v]][best_mapping[nv]]) {
					G[best_mapping[v]].clear(best_mapping[nv]);
					G[best_mapping[nv]].clear(best_mapping[v]);
					goal.push_back(cp);
					score_diff += 100;
				}
			}
		}
		for (int p : goal) {
			while (best_g_emb[p] != v) {
				best_g_emb[p] = v;
				--score_diff;
				if (prev_dir[p] == -1) break;
				p += DN[prev_dir[p]];
			}
		}
		bfs_idx++;
	}
	for (int i = 1; i <= V; ++i) {
		for (int j = 0; j * 64 <= V; ++j) {
			G[i].bits[j] = g_back[i].bits[j];
		}
	}
	debug("finalize score:%d\n", score_diff);
	return score_diff;
}

bool use_complete() {
	if (V <= L) return true;
	return V < 300 && 2 * V <= L2;
}

bool use_sparse() {
	return V > L;
}

void solve() {
	int best_result = 0;
	const int PART = V > 300 ? 1 : V > 200 ? 2 : V > 120 ? 3 : V > 60 ? 4 : V > 30 ? 16 : 100;
	// const int PART = 1;
	update_interval = 100000 / PART;
	vector<decltype(&create_initial_complete)> init_funcs;
	vector<pair<double, double>> sa_params;
	if (use_complete()) {
		init_funcs.push_back(create_initial_complete);
		sa_params.push_back(V > L ? make_pair(0.1, 1.1) : make_pair(1.0, 1.05));
	}
	if (use_sparse()) {
		init_funcs.push_back(create_initial_sparse);
		sa_params.push_back({0.015, PART == 1 ? 1.01 : 1.03});
	}
	int best_idx = -1;
	for (int i = 0; ; ++i) {
		reset();
		const bool use_best = (i >= init_funcs.size() && i >= PART / 2) || i >= init_funcs.size() * 2;
		int func_idx = use_best ? best_idx : i % init_funcs.size();
		init_funcs[func_idx]();
		START_TIMER(0);
		const ll cur_time = get_elapsed_msec();
		if (cur_time >= TL - 40) break;
		const ll timelimit = i >= PART ? TL : cur_time + (TL - cur_time) / (PART - i);
		int result = simulated_annealing(timelimit - 20, sa_params[func_idx].first, sa_params[func_idx].second);
		result += finalize(timelimit);
		STOP_TIMER(0);
		debug("fi:%d score:%d\n", func_idx, result);
		if (result > best_result) {
			best_result = result;
			best_idx = func_idx;
			copy_g_emb(best_g_emb, ans_g_emb);
			copy(best_mapping, best_mapping + V + 1, ans_mapping);
		}
	}
	debug("best_result:%d\n", best_result);
	print_g_emb(ans_g_emb);
}

int main() {
	start_time = get_time();
	scanf("%d %d", &V, &E);
	adj.resize(V + 1);
	for (int i = 0; i < E; ++i) {
		int s, t;
		scanf("%d %d", &s, &t);
		G[s].set(t);
		G[t].set(s);
		adj[s].push_back(t);
		adj[t].push_back(s);
	}
	scanf("%d", &L2);
	L = (int)(sqrt(L2) + 0.1);
	for (int i = 0; i < (1 << 8); ++i) {
		connected[i] = check_connected(i);
	}
	for (int i = 0; i < L; ++i) {
		for (int j = 0; j < L; ++j) {
			int dist = abs(i - L / 2) + abs(j - L / 2);
			positions.push_back((dist << 16) + get_pos(i, j));
		}
	}
	sort(positions.begin(), positions.end());
	for (int i = 0; i < positions.size(); ++i) {
		positions[i] &= 0xFFFF;
	}
	int pos_size = 1;
	while (pos_size < positions.size()) pos_size *= 2;
	pos_size *= 2;
	for (int i = 0; positions.size() < pos_size; ++i) {
		positions.push_back(positions[i]);
	}
	solve();
	vvi ans(V);
	for (int i = 1; i <= L; ++i) {
		for (int j = 1; j <= L; ++j) {
			int v = ans_g_emb[get_pos(i, j)];
			if (v != EMPTY_NODE) {
				ans[ans_mapping[v] - 1].push_back((i - 1) * L + j);
			}
		}
	}
	// debugln();
	// for (int i = 1; i <= L; ++i) {
	// 	for (int j = 1; j <= L; ++j) {
	// 		int v = ans_mapping[ans_g_emb[get_pos(i, j)]];
	// 		debug("%3d ", v);
	// 		for (int k = 0; k < 8; ++k) {
	// 			G[v].clear(ans_mapping[ans_g_emb[get_pos(i + DR[k], j + DC[k])]]);
	// 		}
	// 	}
	// 	debugln();
	// }
	// for (int i = 1; i <= V; ++i) {
	// 	for (int j = i + 1; j <= V; ++j) {
	// 		if (G[i][j]) {
	// 			debug("%d %d\n", i, j);
	// 		}
	// 	}
	// }

	for (int i = 0; i < V; ++i) {
		printf("%d", (int)ans[i].size());
		for (int v : ans[i]) {
			printf(" %d", v);
		}
		printf("\n");
	}
	PRINT_TIMER();
	PRINT_COUNTER();
}

Submission Info

Submission Time
Task A - Problem 2
User tomerun
Language C++14 (Clang 3.8.0)
Score 18824570
Code Size 34366 Byte
Status
Exec Time 29886 ms
Memory 1912 KB

Test Cases

Set Name Score / Max Score Test Cases
random_000 114739 / 1000000 10_random_000
random_001 65869 / 1000000 10_random_001
random_002 10844 / 1000000 10_random_002
random_003 125581 / 1000000 10_random_003
random_004 105594 / 1000000 10_random_004
random_005 133785 / 1000000 10_random_005
random_006 152279 / 1000000 10_random_006
random_007 185029 / 1000000 10_random_007
random_008 33678 / 1000000 10_random_008
random_009 23716 / 1000000 10_random_009
random_010 189678 / 1000000 10_random_010
random_011 182963 / 1000000 10_random_011
random_012 57816 / 1000000 10_random_012
random_013 120227 / 1000000 10_random_013
random_014 38003 / 1000000 10_random_014
random_015 153923 / 1000000 10_random_015
random_016 90170 / 1000000 10_random_016
random_017 143852 / 1000000 10_random_017
random_018 32771 / 1000000 10_random_018
random_019 131813 / 1000000 10_random_019
random_020 206474 / 1000000 10_random_020
random_021 99258 / 1000000 10_random_021
random_022 171831 / 1000000 10_random_022
random_023 96254 / 1000000 10_random_023
random_024 90625 / 1000000 10_random_024
random_025 162301 / 1000000 10_random_025
random_026 107867 / 1000000 10_random_026
random_027 129650 / 1000000 10_random_027
random_028 40066 / 1000000 10_random_028
random_029 147019 / 1000000 10_random_029
random_030 48421 / 1000000 10_random_030
random_031 223963 / 1000000 10_random_031
random_032 185450 / 1000000 10_random_032
random_033 170308 / 1000000 10_random_033
random_034 58339 / 1000000 10_random_034
random_035 187483 / 1000000 10_random_035
random_036 150754 / 1000000 10_random_036
random_037 149388 / 1000000 10_random_037
random_038 129622 / 1000000 10_random_038
random_039 236191 / 1000000 10_random_039
random_040 56665 / 1000000 10_random_040
random_041 81187 / 1000000 10_random_041
random_042 176496 / 1000000 10_random_042
random_043 56478 / 1000000 10_random_043
random_044 123753 / 1000000 10_random_044
random_045 222158 / 1000000 10_random_045
random_046 170533 / 1000000 10_random_046
random_047 149299 / 1000000 10_random_047
random_048 123365 / 1000000 10_random_048
random_049 81586 / 1000000 10_random_049
random_050 111202 / 1000000 10_random_050
random_051 80129 / 1000000 10_random_051
random_052 33175 / 1000000 10_random_052
random_053 108274 / 1000000 10_random_053
random_054 168466 / 1000000 10_random_054
random_055 108683 / 1000000 10_random_055
random_056 94717 / 1000000 10_random_056
random_057 217930 / 1000000 10_random_057
random_058 168314 / 1000000 10_random_058
random_059 160082 / 1000000 10_random_059
random_060 135309 / 1000000 10_random_060
random_061 92687 / 1000000 10_random_061
random_062 87667 / 1000000 10_random_062
random_063 165270 / 1000000 10_random_063
random_064 123642 / 1000000 10_random_064
random_065 188139 / 1000000 10_random_065
random_066 134147 / 1000000 10_random_066
random_067 123530 / 1000000 10_random_067
random_068 109631 / 1000000 10_random_068
random_069 156872 / 1000000 10_random_069
random_070 81416 / 1000000 10_random_070
random_071 64619 / 1000000 10_random_071
random_072 174572 / 1000000 10_random_072
random_073 173809 / 1000000 10_random_073
random_074 170894 / 1000000 10_random_074
random_075 119258 / 1000000 10_random_075
random_076 115518 / 1000000 10_random_076
random_077 179861 / 1000000 10_random_077
random_078 172908 / 1000000 10_random_078
random_079 174771 / 1000000 10_random_079
random_080 170001 / 1000000 10_random_080
random_081 77611 / 1000000 10_random_081
random_082 122521 / 1000000 10_random_082
random_083 151848 / 1000000 10_random_083
random_084 105700 / 1000000 10_random_084
random_085 114377 / 1000000 10_random_085
random_086 112383 / 1000000 10_random_086
random_087 139275 / 1000000 10_random_087
random_088 167104 / 1000000 10_random_088
random_089 30193 / 1000000 10_random_089
random_090 114833 / 1000000 10_random_090
random_091 96826 / 1000000 10_random_091
random_092 152350 / 1000000 10_random_092
random_093 212476 / 1000000 10_random_093
random_094 93240 / 1000000 10_random_094
random_095 76096 / 1000000 10_random_095
random_096 124373 / 1000000 10_random_096
random_097 171184 / 1000000 10_random_097
random_098 68719 / 1000000 10_random_098
random_099 119431 / 1000000 10_random_099
random_100 80384 / 1000000 10_random_100
random_101 201708 / 1000000 10_random_101
random_102 88964 / 1000000 10_random_102
random_103 137380 / 1000000 10_random_103
random_104 144312 / 1000000 10_random_104
random_105 82037 / 1000000 10_random_105
random_106 182168 / 1000000 10_random_106
random_107 166400 / 1000000 10_random_107
random_108 96511 / 1000000 10_random_108
random_109 147868 / 1000000 10_random_109
random_110 123492 / 1000000 10_random_110
random_111 178136 / 1000000 10_random_111
random_112 122688 / 1000000 10_random_112
random_113 181899 / 1000000 10_random_113
random_114 95742 / 1000000 10_random_114
random_115 112738 / 1000000 10_random_115
random_116 192226 / 1000000 10_random_116
random_117 190584 / 1000000 10_random_117
random_118 151618 / 1000000 10_random_118
random_119 26621 / 1000000 10_random_119
random_120 71544 / 1000000 10_random_120
random_121 61195 / 1000000 10_random_121
random_122 87546 / 1000000 10_random_122
random_123 184065 / 1000000 10_random_123
random_124 200074 / 1000000 10_random_124
random_125 63701 / 1000000 10_random_125
random_126 24671 / 1000000 10_random_126
random_127 77280 / 1000000 10_random_127
random_128 110159 / 1000000 10_random_128
random_129 219190 / 1000000 10_random_129
random_130 62492 / 1000000 10_random_130
random_131 82435 / 1000000 10_random_131
random_132 113133 / 1000000 10_random_132
random_133 124257 / 1000000 10_random_133
random_134 168138 / 1000000 10_random_134
random_135 155309 / 1000000 10_random_135
random_136 133512 / 1000000 10_random_136
random_137 142415 / 1000000 10_random_137
random_138 190705 / 1000000 10_random_138
random_139 107764 / 1000000 10_random_139
random_140 212665 / 1000000 10_random_140
random_141 34052 / 1000000 10_random_141
random_142 66715 / 1000000 10_random_142
random_143 19613 / 1000000 10_random_143
random_144 117375 / 1000000 10_random_144
random_145 165657 / 1000000 10_random_145
random_146 174579 / 1000000 10_random_146
random_147 33902 / 1000000 10_random_147
random_148 184588 / 1000000 10_random_148
random_149 191216 / 1000000 10_random_149
Case Name Status Exec Time Memory
10_random_000 29886 ms 1912 KB
10_random_001 29883 ms 896 KB
10_random_002 29882 ms 512 KB
10_random_003 29882 ms 1536 KB
10_random_004 29882 ms 640 KB
10_random_005 29883 ms 768 KB
10_random_006 29884 ms 1536 KB
10_random_007 29883 ms 1408 KB
10_random_008 29882 ms 512 KB
10_random_009 29882 ms 640 KB
10_random_010 29883 ms 1024 KB
10_random_011 29884 ms 1664 KB
10_random_012 29884 ms 1280 KB
10_random_013 29883 ms 512 KB
10_random_014 29883 ms 640 KB
10_random_015 29884 ms 1152 KB
10_random_016 29882 ms 1280 KB
10_random_017 29883 ms 1152 KB
10_random_018 29883 ms 512 KB
10_random_019 29882 ms 1408 KB
10_random_020 29883 ms 1024 KB
10_random_021 29883 ms 1280 KB
10_random_022 29883 ms 1280 KB
10_random_023 29883 ms 1408 KB
10_random_024 29883 ms 1408 KB
10_random_025 29883 ms 640 KB
10_random_026 29884 ms 1536 KB
10_random_027 29882 ms 896 KB
10_random_028 29882 ms 512 KB
10_random_029 29882 ms 768 KB
10_random_030 29883 ms 1152 KB
10_random_031 29883 ms 1792 KB
10_random_032 29883 ms 1280 KB
10_random_033 29883 ms 1280 KB
10_random_034 29883 ms 896 KB
10_random_035 29883 ms 1408 KB
10_random_036 29884 ms 1280 KB
10_random_037 29882 ms 1536 KB
10_random_038 29883 ms 1408 KB
10_random_039 29883 ms 1280 KB
10_random_040 29883 ms 768 KB
10_random_041 29882 ms 640 KB
10_random_042 29882 ms 1536 KB
10_random_043 29884 ms 896 KB
10_random_044 29882 ms 1536 KB
10_random_045 29883 ms 1792 KB
10_random_046 29884 ms 1280 KB
10_random_047 29883 ms 1280 KB
10_random_048 29883 ms 640 KB
10_random_049 29882 ms 896 KB
10_random_050 29883 ms 896 KB
10_random_051 29883 ms 768 KB
10_random_052 29882 ms 512 KB
10_random_053 29882 ms 640 KB
10_random_054 29883 ms 1408 KB
10_random_055 29884 ms 1536 KB
10_random_056 29883 ms 896 KB
10_random_057 29883 ms 1664 KB
10_random_058 29884 ms 1664 KB
10_random_059 29884 ms 1664 KB
10_random_060 29882 ms 1152 KB
10_random_061 29883 ms 896 KB
10_random_062 29882 ms 640 KB
10_random_063 29883 ms 896 KB
10_random_064 29883 ms 896 KB
10_random_065 29884 ms 1536 KB
10_random_066 29883 ms 1536 KB
10_random_067 29884 ms 1152 KB
10_random_068 29883 ms 1024 KB
10_random_069 29883 ms 1280 KB
10_random_070 29883 ms 896 KB
10_random_071 29882 ms 768 KB
10_random_072 29882 ms 768 KB
10_random_073 29882 ms 1536 KB
10_random_074 29882 ms 640 KB
10_random_075 29882 ms 1280 KB
10_random_076 29882 ms 1024 KB
10_random_077 29883 ms 1280 KB
10_random_078 29884 ms 1408 KB
10_random_079 29884 ms 1280 KB
10_random_080 29883 ms 1536 KB
10_random_081 29882 ms 768 KB
10_random_082 29882 ms 1408 KB
10_random_083 29884 ms 1664 KB
10_random_084 29882 ms 512 KB
10_random_085 29882 ms 1152 KB
10_random_086 29882 ms 1024 KB
10_random_087 29883 ms 1024 KB
10_random_088 29884 ms 1280 KB
10_random_089 29882 ms 512 KB
10_random_090 29883 ms 1024 KB
10_random_091 29883 ms 1280 KB
10_random_092 29883 ms 1408 KB
10_random_093 29883 ms 1408 KB
10_random_094 29882 ms 896 KB
10_random_095 29882 ms 768 KB
10_random_096 29882 ms 1280 KB
10_random_097 29883 ms 1408 KB
10_random_098 29883 ms 1024 KB
10_random_099 29882 ms 1280 KB
10_random_100 29883 ms 1280 KB
10_random_101 29884 ms 1664 KB
10_random_102 29882 ms 1024 KB
10_random_103 29882 ms 640 KB
10_random_104 29883 ms 896 KB
10_random_105 29883 ms 896 KB
10_random_106 29882 ms 1408 KB
10_random_107 29883 ms 1280 KB
10_random_108 29883 ms 1024 KB
10_random_109 29884 ms 1408 KB
10_random_110 29873 ms 512 KB
10_random_111 29883 ms 1664 KB
10_random_112 29884 ms 1280 KB
10_random_113 29883 ms 1408 KB
10_random_114 29882 ms 1152 KB
10_random_115 29883 ms 1152 KB
10_random_116 29883 ms 896 KB
10_random_117 29883 ms 1280 KB
10_random_118 29883 ms 1384 KB
10_random_119 29882 ms 896 KB
10_random_120 29882 ms 896 KB
10_random_121 29883 ms 640 KB
10_random_122 29883 ms 1280 KB
10_random_123 29883 ms 1408 KB
10_random_124 29883 ms 1280 KB
10_random_125 29885 ms 1536 KB
10_random_126 29883 ms 512 KB
10_random_127 29883 ms 640 KB
10_random_128 29883 ms 384 KB
10_random_129 29882 ms 1152 KB
10_random_130 29882 ms 1024 KB
10_random_131 29884 ms 1408 KB
10_random_132 29883 ms 1152 KB
10_random_133 29884 ms 1024 KB
10_random_134 29883 ms 1664 KB
10_random_135 29883 ms 1536 KB
10_random_136 29884 ms 1408 KB
10_random_137 29884 ms 1408 KB
10_random_138 29883 ms 1536 KB
10_random_139 29882 ms 768 KB
10_random_140 29883 ms 1280 KB
10_random_141 29883 ms 512 KB
10_random_142 29882 ms 1024 KB
10_random_143 29882 ms 640 KB
10_random_144 29883 ms 1408 KB
10_random_145 29883 ms 1024 KB
10_random_146 29882 ms 1152 KB
10_random_147 29883 ms 512 KB
10_random_148 29883 ms 1280 KB
10_random_149 29884 ms 1664 KB