Submission #67393137

---

Source Code Expand

// #pragma GCC optimize("O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <assert.h>

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#define dump(x) cerr << #x << " = " << (x) << endl;

using namespace std;

const int64_t CYCLES_PER_SEC = 2900000000;
const double TIMELIMIT = 1.95;
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);
	}
};
Timer timer;
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);
	}

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


const int N = 40;
const int N2 = N * N;
const int N2MMAX = N2 - (N2 / 10);
struct FastSet2 {
	int N;
	int list[N2MMAX];
	int pos[N2MMAX];
	int sz;
	void init(int _N) {
		N = _N;
		sz = 0;
		for (int i = 0; i < N; i++) {
			pos[i] = list[i] = i;
		}
	}
	void insert_all() {
		sz = N;
	}
	int getAny() {
		return list[sz++];
	}
	void insert(int a) {
		if (pos[a] >= sz) {
			pos[list[sz]] = pos[a];
			swap(list[pos[a]], list[sz]);
			pos[a] = sz;
			sz++;
		}
	}
	void erase(int a) {
		if (pos[a] < sz) {
			sz--;
			pos[list[sz]] = pos[a];
			swap(list[pos[a]], list[sz]);
			pos[a] = sz;
		}
	}
	inline int size() {
		return sz;
	}
	inline int rand() {
		return list[rnd.nextInt(sz)];
	}
	inline void erase_all() {
		sz = 0;
	}
};

const int DX[4] = {1, 0, -1, 0};
const int DY[4] = {0, 1, 0, -1};
const int REV[4] = {2, 3, 0, 1};
const string DIR = "DRUL";

int N2M;  // Number of empty cells
int M;
int B[N][N];
int neighbor[N2MMAX][4];
int empty_to_original_X[N2MMAX];
int empty_to_original_Y[N2MMAX];
int to_converted_index[N2];
short initial_ice_board[4][N2MMAX];
double initial_probability[N2MMAX];
short get_initial_ice_board(int k, int i) {
	if (initial_ice_board[k][i] == -1) {
		if (neighbor[i][k] == -1) {
			initial_ice_board[k][i] = i;
		} else {
			initial_ice_board[k][i] = get_initial_ice_board(k, neighbor[i][k]);
		}
	}
	return initial_ice_board[k][i];
}

void calc_next_probability(double cur[N2MMAX], double ne[N2MMAX], short initial_ice_board[4][N2MMAX], FastSet2& empty_cells) {
	for (int i = 0; i < empty_cells.size(); i++) {
		int idx = empty_cells.list[i];
		ne[idx] = 0;
	}
	for (int i = 0; i < empty_cells.size(); i++) {
		int idx = empty_cells.list[i];
		for (int k = 0; k < 4; k++) {
			int next_idx = initial_ice_board[k][idx];
			ne[next_idx] += cur[idx] / 4.0;
		}
	}
}

void init() {
	for (int i = 0; i < N2; i++) {
		int x = i / N;
		int y = i % N;
		if (B[x][y] == 0) {
			for (int k = 0; k < 4; k++) {
				int nx = x + DX[k];
				int ny = y + DY[k];
				if (nx >= 0 && nx < N && ny >= 0 && ny < N && B[nx][ny] == 0) {
					neighbor[to_converted_index[i]][k] = to_converted_index[nx * N + ny];
				} else {
					neighbor[to_converted_index[i]][k] = -1;
				}
			}
		}
	}
	for (int i = 0; i < N2M; i++) {
		for (int k = 0; k < 4; k++) {
			initial_ice_board[k][i] = -1;
		}
	}
	for (int i = 0; i < N2M; i++) {
		for (int k = 0; k < 4; k++) {
			get_initial_ice_board(k, i);
		}
	}

	double uniform_probability[N2MMAX];
	for (int i = 0; i < N2M; i++) {
		uniform_probability[i] = 1.0 / N2M;
	}
	FastSet2 empty_cells;
	empty_cells.init(N2M);
	empty_cells.insert_all();
	calc_next_probability(uniform_probability, initial_probability, initial_ice_board, empty_cells);
}

void put_stone(int idx, FastSet2& empty_cells, double cur[N2MMAX], double ne[N2MMAX], short ice_board[4][N2MMAX]) {
	empty_cells.erase(idx);
	if (empty_cells.size() == 0) {
		return;
	}
	// update ice board
	for (int k = 0; k < 4; k++) {
		if (neighbor[idx][k] == -1 || empty_cells.pos[neighbor[idx][k]] >= empty_cells.size()) {
			continue;
		}
		int reach_idx = neighbor[idx][k];
		int n_idx = reach_idx;
		ice_board[REV[k]][n_idx] = reach_idx;
		while (neighbor[n_idx][k] != -1 && empty_cells.pos[neighbor[n_idx][k]] < empty_cells.size()) {
			n_idx = neighbor[n_idx][k];
			ice_board[REV[k]][n_idx] = reach_idx;
		}
	}

	// update probability
	calc_next_probability(cur, ne, ice_board, empty_cells);
}

void put_stone_only(int idx, FastSet2& empty_cells, short ice_board[4][N2MMAX]) {
	empty_cells.erase(idx);
	if (empty_cells.size() == 0) {
		return;
	}
	// update ice board
	for (int k = 0; k < 4; k++) {
		if (neighbor[idx][k] == -1 || empty_cells.pos[neighbor[idx][k]] >= empty_cells.size()) {
			continue;
		}
		int reach_idx = neighbor[idx][k];
		int n_idx = reach_idx;
		ice_board[REV[k]][n_idx] = reach_idx;
		while (neighbor[n_idx][k] != -1 && empty_cells.pos[neighbor[n_idx][k]] < empty_cells.size()) {
			n_idx = neighbor[n_idx][k];
			ice_board[REV[k]][n_idx] = reach_idx;
		}
	}
}
struct Params {
	int phase1;
	double weight;
	Params(int _phase1, double _weight) : phase1(_phase1), weight(_weight) {}
};
double solve_greedy(FastSet2& empty_cells, int order[], Params& params) {
	empty_cells.insert_all();

	double cur[N2MMAX];
	double ne[N2MMAX];
	for (int i = 0; i < N2M; i++) {
		cur[i] = initial_probability[i];
		ne[i] = 0;
	}

	short ice_board[4][N2MMAX];
	for (int k = 0; k < 4; k++) {
		for (int i = 0; i < N2M; i++) {
			ice_board[k][i] = initial_ice_board[k][i];
		}
	}

	double score = 0;
	double accumulated_probability = 0;
	for (int i = 0; i < N2M; i++) {
		int best_idx = -1;
		double best_eval = -1e9;

		for (int _j = 0; _j < empty_cells.size(); _j++) {
			int idx = empty_cells.list[_j];
			double eval = -1e4 * cur[idx];
			if (i > 0) {
				for (int k = 0; k < 4; k++) {
					if (i < params.phase1) {
						if (neighbor[idx][k] == -1 || empty_cells.pos[neighbor[idx][k]] >= empty_cells.size()) {
							continue;
						}
						if (ne[neighbor[idx][k]] > cur[neighbor[idx][k]]) {
							eval += 1 * cur[neighbor[idx][k]];
						} else {
							eval += params.weight * cur[neighbor[idx][k]];
						}
					} else {
						eval -= cur[ice_board[k][idx]];
						if (neighbor[idx][k] == -1 || empty_cells.pos[neighbor[idx][k]] >= empty_cells.size()) {
							continue;
						}
						if (ne[neighbor[idx][k]] > cur[neighbor[idx][k]]) {
							eval += 1e-5 * cur[neighbor[idx][k]];
						} else {
							eval += 1e-5 * cur[neighbor[idx][k]];
						}
					}
				}
			}

			if (eval > best_eval) {
				best_eval = eval;
				best_idx = idx;
			}
		}

		order[i] = best_idx;

		accumulated_probability += cur[best_idx];
		score += accumulated_probability;
		put_stone(best_idx, empty_cells, cur, ne, ice_board);
		swap(cur, ne);
	}
	return score;
}

void solve() {
	// vector<int> start_order = solve_cycle();
	FastSet2 empty_cells;
	empty_cells.init(N2M);
	double best_score = 1e9;
	Params params(30, 10.0);
	Params best_params(30, 10.0);
	int best_order[N2M];
	int cnt = 0;
	while (true) {
		cnt++;
		double ti = timer.get();
		if (ti > TIMELIMIT) {
			break;
		}
		
		int order[N2M];
		double rand_weight = rnd.nextDouble();
		if (rand_weight < 0.5) {
			params.phase1 += rnd.nextInt(7) - 3;
		} else {
			params.weight += rnd.nextDouble() * 2 - 1;
		}

		double score = solve_greedy(empty_cells, order, params);
		if (score < best_score) {
			best_score = score;
			best_params = params;
			for (int i = 0; i < N2M; i++) {
				best_order[i] = order[i];
			}
			cerr << "best_score = " << best_score << endl;
			cerr << "params = " << params.phase1 << " " << params.weight << endl;
		}else{
			params = best_params;
		}
	}
	cerr << "cnt = " << cnt << endl;
	cerr << "score = " << 1e6 * (N2M - best_score) / (N2M - 1) << endl;
	for (int i = 0; i < N2M; i++) {
		int x = empty_to_original_X[best_order[i]];
		int y = empty_to_original_Y[best_order[i]];
		cout << x << " " << y << endl;
	}
}

void input() {
	int _;
	int _M;
	cin >> _ >> _M;
	string s;
	M = 0;
	for (int i = 0; i < N; i++) {
		cin >> s;
		for (int j = 0; j < N; j++) {
			if (s[j] == '#') {
				B[i][j] = 1;
			} else {
				B[i][j] = 0;
				empty_to_original_X[M] = i;
				empty_to_original_Y[M] = j;
				to_converted_index[i * N + j] = M;
				M++;
			}
		}
	}
	M = N2 - M;
	assert(M == _M);
	N2M = N2 - M;
}

int main(int argc, char* argv[]) {
	input();
	init();
	solve();
	cerr << "timer = " << timer.get() << endl;
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main(int, char**)’:
Main.cpp:393:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
  393 | int main(int argc, char* argv[]) {
      |          ~~~~^~~~
Main.cpp:393:26: warning: unused parameter ‘argv’ [-Wunused-parameter]
  393 | int main(int argc, char* argv[]) {
      |                    ~~~~~~^~~~~~

Judge Result