Submission #18619499

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <array>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <cstring>
#include <unordered_map>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

struct Timer{
    chrono::high_resolution_clock::time_point st;

    Timer() { reset(); }

    void reset(){
        st = chrono::high_resolution_clock::now();
    }

    chrono::milliseconds::rep elapsed(){
        auto ed = chrono::high_resolution_clock::now();
        return chrono::duration_cast<chrono::milliseconds>(ed - st).count();
    }
};

struct RNG{
    mt19937 mt;

    RNG() : mt(chrono::steady_clock::now().time_since_epoch().count()){}

    int operator()(int a, int b){
        uniform_int_distribution<int> dist(a, b - 1);
        return dist(mt);
    }

    int operator()(int b){
        return (*this)(0, b);
    }
};

Timer timekeeper;
RNG rng;
constexpr int H = 50;
constexpr int W = 50;
constexpr int K = 8;
constexpr int dx[4] = {1, 0, -1, 0};
constexpr int dy[4] = {0, 1, 0, -1};
int grid[H][W];
bool used[H][W];
vector<P> ps;
vector<vector<P>> ans;
priority_queue<P> que;

inline void input(){
    int __;
    cin >> __ >> __ >> __;
    for(int r = 0; r < H; ++r){
        for(int c = 0; c < W; ++c){
            char ch;
            cin >> ch;
            grid[r][c] = ch - '0';
            if(grid[r][c] > 0){
                que.emplace(grid[r][c], W * r + c);
            }
        }
    }
}

inline ll evaluate(){
    ll res = 0;
    int n = ans.size();
    for(int i = 0; i < n; ++i){
        ll sum = 1;
        for(auto [r, c] : ans[i])   sum *= grid[r][c];
        res += sum;
    }
    res = (res + 9999) / 10000;
    return res;
}

bool dfs(int r, int c){
    ps.emplace_back(r, c);
    used[r][c] = true;
    if((int)ps.size() == K){
        ans.emplace_back(ps);
        ps.pop_back();
        return true;
    }
    for(int i = 0; i < 4; ++i){
        int nr = r + dx[i], nc = c + dy[i];
        if(nr < 0 || nr >= H || nc < 0 || nc >= W)  continue;
        if(used[nr][nc] || grid[nr][nc] == 0)   continue;
        if(dfs(nr, nc)){
            ps.pop_back();
            return true;
        }
    }
    ps.pop_back();
    return used[r][c] = false;
}

void greedy(){
    // for(int r = 0; r < H; ++r){
    //     for(int c = 0; c < W; ++c){
    //         if(!used[r][c]) dfs(r, c);
    //     }
    // }
    while(!que.empty()){
        auto [num, p] = que.top();
        que.pop();
        int r = p / W, c = p % W;
        if(!used[r][c]) dfs(r, c);
    }
}

void search(){
    int n = ans.size();
    // while(timekeeper.elapsed() <= 9000){
        for(int i = 0; i < n; ++i){
            auto [r1, c1] = ans[i][0];
            auto [r2, c2] = ans[i][K - 1];
            int maxe, lb = 1, ub = K, swap_id = 0;
            if(grid[r1][c1] > grid[r2][c2]){
                swap(r1, r2);
                swap(c1, c2);
                lb = 0, ub = K - 1, swap_id = K - 1;
            }
            maxe = grid[r1][c2];
            int next_r = -1, next_c = -1;
            for(int j = lb; j < ub; ++j){
                auto [r, c] = ans[i][j];
                for(int k = 0; k < 4; ++k){
                    int nr = r + dx[k], nc = c + dy[k];
                    if(nr < 0 || nr >= H || nc < 0 || nc >= W)  continue;
                    if(used[nr][nc] || grid[nr][nc] == 0)   continue;
                    if(chmax(maxe, grid[nr][nc])){
                        next_r = nr, next_c = nc;
                    }
                }
            }
            if(next_c != -1){
                used[r1][r2] = false;
                ans[i][swap_id] = P(next_r, next_c);
                used[next_r][next_c] = true;
            }
        }
    // }
}

inline void output(){
    int n =  ans.size();
    cout << n << '\n';
    for(int i = 0; i < n; ++i){
        for(auto [r, c] : ans[i])   cout << r + 1 << ' ' << c + 1 << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    input();
    greedy();
    search();
    // cout << evaluate() << endl;
    output();
}

Submission Info

Judge Result