Submission #18619907


Source Code Expand

Copy
#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;
vector<P> RC[10];

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';
            RC[grid[r][c]].emplace_back(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;
    }
    vector<tuple<int, int, int>> dat;
    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])    continue;
        dat.emplace_back(grid[nr][nc], nr, nc);
    }
    sort(dat.rbegin(), dat.rend());
    for(auto [num, nr, nc] : dat){
        if(dfs(nr, nc)){
            ps.pop_back();
            return true;
        }
    }
    ps.pop_back();
    return used[r][c] = false;
}

void random_greedy(){
    for(int k = 9; k >= 1; --k){
        int cnt = 0;
        while(RC[k].size() && cnt < 100000000 && timekeeper.elapsed() <= 9850){
            shuffle(RC[k].begin(), RC[k].end(), rng.mt);
            for(int loop = 0; loop < 100; ++loop){
                if(!RC[k].size())   break;
                auto [r, c] = RC[k].back();
                if(used[r][c])  RC[k].pop_back();
                else{
                    if(dfs(r, c))   RC[k].pop_back();
                }
            }
            cnt += 100;
        }
    }
}

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();
    random_greedy();
    output();
}

Submission Info

Submission Time
Task A - Multiple Pieces
User outline
Language C++ (GCC 9.2.1)
Score 426904
Code Size 4017 Byte
Status AC
Exec Time 9858 ms
Memory 3732 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 45850 / 1343058 43552 / 1343058 41180 / 1343058 36346 / 1343058 44291 / 1343058 43029 / 1343058 43639 / 1343058 43203 / 1343058 42574 / 1343058 43240 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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 9858 ms 3732 KB
subtask_01_02.txt AC 9853 ms 3656 KB
subtask_01_03.txt AC 9853 ms 3696 KB
subtask_01_04.txt AC 9853 ms 3664 KB
subtask_01_05.txt AC 9854 ms 3704 KB
subtask_01_06.txt AC 9853 ms 3644 KB
subtask_01_07.txt AC 9853 ms 3684 KB
subtask_01_08.txt AC 9854 ms 3664 KB
subtask_01_09.txt AC 9853 ms 3648 KB
subtask_01_10.txt AC 9853 ms 3696 KB