#include <bits/stdc++.h>
using namespace std;
const int maxn = 303, tries = 100, lives = 10, 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;
}
}
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
K = 21 |
| 2 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
