Submission #3887428

---

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 = 5, 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

Judge Result