Submission #786087

#	Time	Username	Problem	Language	Result	Execution time	Memory
786087		vjudge1	Coins (LMIO19_monetos)	C++17	8.01 / 100	1736 ms	1380 KiB

monetos

#include <bits/stdc++.h>
using namespace std;

const int maxn = 303, tries = 10, lives = 100000, tolerance = 0;
int t, n, k1, k2;
vector<vector<bool>> board;

int sum;
vector<int> rows;
int pref[maxn][maxn];
mt19937 rng;

int score;
vector<int> solution;
int cur_score;
vector<int> cur_solution;

void init() {
	sum = 0;
	memset(pref, 0, sizeof pref);
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			rows.push_back(i);
			if (!board[i][j]) {
				sum++;
				pref[i][j] = 1;
			}
		}
	}

	for (int i=0; i<n; i++) {
		for (int j=1; j<n; j++) {
			pref[i][j] += pref[i][j-1];
		}
	}

	rng = mt19937((unsigned long long) new char);
}

void init_solution() { // distribusi normal kayaknya, O(n^2)
	shuffle(rows.begin(), rows.end(), rng);

	cur_solution = vector<int>(n, 0);
	for (int i=0; i<sum; i++) cur_solution[rows[i]]++;
	sort(cur_solution.rbegin(), cur_solution.rend());
}

int get_score(const vector<int> &sol) { // O(n)
	int ret = 0;
	for (int i=0; i<n; i++) ret += sol[i] - (sol[i] == 0 ? 0 : pref[i][sol[i]-1]);
	return ret;
}

pair<pair<int, int>, int> move() { // O(n)
	vector<int> us;
	for (int i=0; i<n; i++) {
		if (cur_solution[i] && (i+1 == n || cur_solution[i] > cur_solution[i+1])) {
			us.push_back(i);
		}
	}

	vector<int> vs;
	vs.push_back(0);
	for (int i=1; i<n; i++) {
		if (cur_solution[i-1] > cur_solution[i]) {
			vs.push_back(i);
		}
	}

	int u = us[rng() % us.size()], v = vs[rng() % vs.size()];
	int diff = 
		cur_solution[u] - 1 - (cur_solution[u] == 1 ? 0 : pref[u][cur_solution[u]-2]) + 
		cur_solution[v] + 1 - pref[v][cur_solution[v]] -
		cur_solution[u] - (cur_solution[u] == 1 ? 0 : pref[u][cur_solution[u]-1]) - 
		cur_solution[v] - (cur_solution[v] == 1 ? 0 : pref[v][cur_solution[v]-1]);
	cur_solution[u]--;
	cur_solution[v]++;

	return make_pair(make_pair(u, v), diff); 
}

void undo_move(const pair<int, int> &move) { // O(1)
	cur_solution[move.first]++;
	cur_solution[move.second]--;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> t >> n >> k1 >> k2;
	// if (t != 1) return 0;
	board.resize(n);
	for (int i=0; i<n; i++) {
		board[i].resize(n);
		for (int j=0; j<n; j++) {
			int a;
			cin >> a;
			board[i][j] = a;
		}
	}

	init();

	score = 1e9;
	for (int _t=0; _t<tries; _t++) {
		init_solution();
		cur_score = get_score(cur_solution);

		for (int l=0; l<lives; ) {
			auto res = move();
			pair<int, int> &move = res.first;
			int &diff = res.second;
			if (diff <= tolerance) {
				undo_move(move);
				l++;
			} else {
				cur_score += diff;
				l = 0;
			} 
		}

		if (cur_score < score) {
			swap(solution, cur_solution);
			swap(score, cur_score);
		}
	}

	for (int i=0; i<n; i++) {
		for (int j=0; j<solution[i]; j++) cout << "0 ";
		for (int j=solution[i]; j<n; j++) cout << "1 ";
		cout << '\n';
	}
	return 0;
}

• Subtask 1: 8.008244775 / 100