#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;
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());
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) || make_pair(v, u) == prev_move) {
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
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
174 ms |
596 KB |
K = 17 |
| 2 |
Incorrect |
456 ms |
700 KB |
K = 602 |
| 3 |
Incorrect |
1783 ms |
1364 KB |
K = 21060 |
| 4 |
Partially correct |
1758 ms |
1364 KB |
K = 23003 |
| 5 |
Partially correct |
1876 ms |
1348 KB |
K = 18254 |
| 6 |
Partially correct |
1687 ms |
1364 KB |
K = 22064 |
| 7 |
Partially correct |
1794 ms |
1364 KB |
K = 22617 |
| 8 |
Execution timed out |
2083 ms |
1364 KB |
Time limit exceeded |
| 9 |
Partially correct |
1721 ms |
1364 KB |
K = 21063 |
| 10 |
Partially correct |
1955 ms |
1364 KB |
K = 22523 |
