Submission #18618682


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;
}

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;

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';
        }
    }
}

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])    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);
        }
    }
}

inline void output(){
    cout << ans.size() << '\n';
    for(int i = 0; i < (int)ans.size(); ++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();
    output();
}

Submission Info

Submission Time
Task A - Multiple Pieces
User outline
Language C++ (GCC 9.2.1)
Score 57476
Code Size 2393 Byte
Status AC
Exec Time 9 ms
Memory 3664 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 5056 / 1343058 5984 / 1343058 7002 / 1343058 4788 / 1343058 3771 / 1343058 6558 / 1343058 6039 / 1343058 3923 / 1343058 6536 / 1343058 7819 / 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 9 ms 3664 KB
subtask_01_02.txt AC 2 ms 3532 KB
subtask_01_03.txt AC 3 ms 3532 KB
subtask_01_04.txt AC 3 ms 3632 KB
subtask_01_05.txt AC 4 ms 3528 KB
subtask_01_06.txt AC 3 ms 3528 KB
subtask_01_07.txt AC 3 ms 3636 KB
subtask_01_08.txt AC 5 ms 3628 KB
subtask_01_09.txt AC 2 ms 3664 KB
subtask_01_10.txt AC 2 ms 3600 KB