竞赛讨论区 > E rand过去了, 这真的合理吗
头像
1扇子秒元歌
编辑于 03-10 21:28
+ 关注

E rand过去了, 这真的合理吗

#include <bits/stdc++.h>


#if __cplusplus >= 202002L
namespace stdv = std::views;
namespace stdr = std::ranges;
#endif


template <typename T> constexpr auto enumerate(const T& vec) { std::vector<std::pair<int, typename T::value_type>> result(vec.size());for (int i = 0; i < vec.size(); i++) { result[i] = std::pair(i, vec[i]); } return result; }
template <typename P, typename Q> constexpr std::istream& operator>>(std::istream& is, std::pair<P, Q>& v) { is >> v.first >> v.second; return is; }
template <typename P, typename Q> constexpr std::ostream& operator<<(std::ostream& os, const std::pair<P, Q>& v) { os << v.first << ' ' << v.second; return os; }
template <typename ...Args> constexpr std::istream& operator>>(std::istream& is, std::tuple<Args...>& v) { std::apply([&is](auto&... args) {((is >> args), ...);}, v); return is; }
template <typename ...Args> constexpr std::ostream& operator<<(std::ostream& os, const std::tuple<Args...>& v) { std::apply([&os](auto&&... args) {((os << args << ' '), ...);}, v); return os; }
template <typename T, std::size_t N> constexpr std::istream& operator>>(std::istream& is, std::array<T, N>& v) { for (auto& i : v) is >> i; return is; }
template <typename T, std::size_t N> constexpr std::ostream& operator<<(std::ostream& os, const std::array<T, N>& v) { for (int i = 0; i < v.size(); i++) os << v[i] << (std::is_class_v<T> ? "\n" : i + 1 != v.size() ? " " : ""); return os; }
template <typename T> constexpr std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto& i : v) is >> i; return is; }
template <typename T> constexpr std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) { for (int i = 0; i < v.size(); i++) { os << v[i] << (std::is_class_v<T> ? "\n" : i + 1 != v.size() ? " " : ""); } return os; }
template <typename...Args> constexpr void print(Args&&...args) { ((std::cout << args << ' '), ...); }
template <typename...Args> constexpr void debug(Args&&...args) { ((std::cerr << args << ' '), ...); std::cerr << '\n'; }
template <typename...Args> constexpr void println(Args&&...args) { ((std::cout << args << ' '), ...); std::cout << '\n'; }
template <typename P, typename Q> constexpr bool chmax(P& a, Q b) { a = (b > a ? b : a); return a == b; }
template <typename P, typename Q> constexpr bool chmin(P& a, Q b) { a = (b < a ? b : a); return a == b; }
template <typename T> static constexpr T inf = std::numeric_limits<T>::max() / 2;
template <typename T> constexpr void discretize(std::vector<T>& v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); }


using i64 = int64_t;


std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());


constexpr int N = 1000;


char s[N][N];
int dis[N][N];


std::pair<int, int> dir[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };


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


    int n, m;
    std::cin >> n >> m;


    auto check = [&]() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dis[i][j] = -1;
            }
        }
        dis[0][0] = 0;
        std::queue<std::pair<int, int>> q;
        q.emplace(0, 0);
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();


            for (auto [dx, dy] : dir) {
                int u = x + dx;
                int v = y + dy;
                if (u < 0 || u >= n || v < 0 || v >= m || dis[u][v] != -1 || s[x][y] == s[u][v]) {
                    continue;
                }
                dis[u][v] = dis[x][y] + 1;
                q.emplace(u, v);
            }
        }
        int t = dis[n - 1][m - 1];
        return t != -1 && t != n * m - 1 && t != n + m - 2;
    };


    const int P = std::abs(n - m) >= 700 ? 10 : 3;
    do {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                s[i][j] = char(rnd() % P + 'a');
            }
        }
    } while (!check());


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cout << s[i][j];
        }
        std::cout << "\n";
    }


    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐