Submission #3887464
Source Code Expand
#include <chrono>
#include <set>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
#define H 50
#define W 50
#define K 8
int input[H][W];
typedef pair<short, short> P;
int dirx[] = {1, -1, 0, 0}, diry[] = {0, 0, 1, -1};
bool used[H][W];
vector<P> cache[H][W];
unsigned int xor128() {
static unsigned int x=123456789, y=362436069, z=521288629, w=88675123;
unsigned int t;
t=(x^(x<<11)); x=y; y=z; z=w;
return (w=(w^(w>>19))^(t^(t>>8)));
}
long long solve(vector<P> &ans) {
long long total_score = 0;
memset(used, 0, sizeof(used));
for (;;) {
int best_score = -1;
vector<P> best_piece(K), piece(K);
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) {
if (used[i][j] || input[i][j] == 0) continue;
bool need_calc = cache[i][j].size() != K;
for (P p : cache[i][j])
if (used[p.first][p.second]) { need_calc = true; break; }
int count = 0;
if (need_calc) {
priority_queue<pair<int, P> > pq;
pq.push(make_pair(input[i][j], make_pair(i, j)));
while (!pq.empty()) {
int i0 = pq.top().second.first, j0 = pq.top().second.second;
pq.pop();
if (used[i0][j0]) continue;
piece[count++] = make_pair(i0, j0);
used[i0][j0] = true;
if (count == K) break;
for (int k = 0; k < 4; k++) {
int i1 = i0 + diry[k], j1 = j0 + dirx[k];
if (0 <= i1 && i1 < H && 0 <= j1 && j1 < W && !used[i1][j1]
&& input[i1][j1] > 0) {
pq.push(make_pair(input[i1][j1]*32 + xor128()%32, make_pair(i1, j1)));
}
}
}
// if K != count, then connected component of (i,
// j) has less than K blocks so cells in this
// component can never be a part of other pieces;
// thus they are left marked for pruning
if (K != count) continue;
} else {
piece = cache[i][j];
}
int score = 1;
for (auto p : piece) score *= input[p.first][p.second];
if (score > best_score || score == best_score && xor128()%3) {
best_score = score;
best_piece = piece;
}
for (auto p : piece) used[p.first][p.second] = false;
cache[i][j] = piece;
}
if (best_score > 0) {
ans.insert(ans.end(), best_piece.begin(), best_piece.end());
for (auto p : best_piece) used[p.first][p.second] = true;
total_score += best_score;
}
else break;
}
return total_score;
}
int main() {
int dur = 0, margin = 60, timelimit = 10000;
auto start = chrono::system_clock::now();
int h, w, k;
cin >> h >> w >> k;
for (int i = 0; i < H; i++) {
string s; cin >> s;
for (int j = 0; j < W; j++) input[i][j] = s[j]-'0';
}
vector<P> temp;
long long best_score = 0;
vector<P> best_seq;
int iter = 0;
while (dur + margin < timelimit) {
iter++;
temp.clear();
long long score = solve(temp);
if (best_score < score) {
best_score = score;
best_seq = temp;
cerr << dur << ' ' << iter << ' ' << score << endl;
}
dur = chrono::duration_cast<std::chrono::milliseconds>(chrono::system_clock::now() - start).count();
}
cerr << iter << endl;
cout << best_seq.size() / K << endl;
for (P x : best_seq) cout << x.first + 1 << ' ' << x.second + 1 << endl;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
kozima |
Language |
C++14 (GCC 5.4.1) |
Score |
941841 |
Code Size |
4123 Byte |
Status |
AC |
Exec Time |
9955 ms |
Memory |
512 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
94412 / 1343058 |
89706 / 1343058 |
96731 / 1343058 |
89417 / 1343058 |
101922 / 1343058 |
91515 / 1343058 |
97707 / 1343058 |
87267 / 1343058 |
97777 / 1343058 |
95387 / 1343058 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
9945 ms |
512 KB |
subtask_01_02.txt |
AC |
9947 ms |
512 KB |
subtask_01_03.txt |
AC |
9953 ms |
512 KB |
subtask_01_04.txt |
AC |
9950 ms |
512 KB |
subtask_01_05.txt |
AC |
9955 ms |
512 KB |
subtask_01_06.txt |
AC |
9946 ms |
512 KB |
subtask_01_07.txt |
AC |
9951 ms |
512 KB |
subtask_01_08.txt |
AC |
9945 ms |
512 KB |
subtask_01_09.txt |
AC |
9953 ms |
512 KB |
subtask_01_10.txt |
AC |
9954 ms |
512 KB |