oj.uz

Submission #787940

# Submission time Handle Problem Language Result Execution time Memory
787940 2023-07-19T14:57:21 Z vjudge1 Coins (LMIO19_monetos) C++17
19.8321 / 100
 91 ms 1364 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 303, tries = 5, lives = 10000, 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;
pair<int, int> prev_move;
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());
	
	cur_solution = vector<int>(n);
	for (int i=0; i<sum%n; i++) cur_solution[i] = (sum+n-1)/n;
	for (int i=sum%n; i<n; i++) cur_solution[i] = sum/n;
	
	prev_move = {0, 0};
}

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()];
	while (u == v || (u == v-1 && cur_solution[u] == cur_solution[v] + 1)) {
		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] == 0 ? 0 : pref[u][cur_solution[u]-1])) - 
		(cur_solution[v] - (cur_solution[v] == 0 ? 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]--;
}

void print_board(const vector<int> &sol) {
	for (int i=0; i<n; i++) {
		for (int j=0; j<sol[i]; j++) cout << "0 ";
		for (int j=sol[i]; j<n; j++) cout << "1 ";
		cout << '\n';
	}
}

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 == 0) {
				prev_move = move;
				l++;
			} else if (diff > 0) {
				undo_move(move);
				l++;
			} else {
				prev_move = move;
				cur_score += diff;
				l = 0;
			}
		}

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

	print_board(solution);
	return 0;
}

/*
0 4 0 0
1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
*/

Subtask #1
19.8321474411 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 684 KB K = 17
2 Incorrect 21 ms 596 KB K = 604
3 Incorrect 71 ms 1364 KB K = 21141
4 Partially correct 63 ms 1364 KB K = 23239
5 Partially correct 90 ms 1364 KB K = 18256
6 Partially correct 91 ms 1364 KB K = 22245
7 Incorrect 76 ms 1328 KB K = 22811
8 Partially correct 80 ms 1364 KB K = 20037
9 Partially correct 79 ms 1364 KB K = 21031
10 Partially correct 85 ms 1364 KB K = 22606