Submission #1163410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163410		xnscdev	Sateliti (COCI20_satellti)	C++20	110 / 110	503 ms	135028 KiB

Main

// https://oj.uz/problem/view/COCI20_satellti

#ifndef DEBUG
#pragma GCC optimize("Ofast,unroll-loops")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#if defined(DEBUG) && defined(DEBUG_UTIL)
#include "dsa_util.h"
#endif

// clang-format off
using namespace std;
using namespace __gnu_pbds;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

constexpr int INF = 0x3f3f3f3f;
constexpr ll INFL = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-9;
constexpr int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
constexpr int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
constexpr int drev[8] = {1, 0, 3, 2, 7, 6, 5, 4};
constexpr int drotl[8] = {2, 3, 1, 0, 6, 4, 7, 5};
constexpr int drotr[8] = {3, 2, 0, 1, 5, 7, 4, 6};
constexpr char dn_nsew[4] = {'S', 'N', 'E', 'W'};
constexpr char dn_udrl[4] = {'D', 'U', 'R', 'L'};
unordered_map<char, int> dm_nsew = {{'S', 0}, {'N', 1}, {'E', 2}, {'W', 3}};
unordered_map<char, int> dm_udrl = {{'D', 0}, {'U', 1}, {'R', 2}, {'L', 3}};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#if __cplusplus < 202002L
template <typename T> int popcount(T x); template <> int popcount(uint x) { return __builtin_popcount(x); } template <> int popcount(ull x) { return __builtin_popcountll(x); }
template <typename T> int countl_zero(T x); template <> int countl_zero(uint x) { return __builtin_clz(x); } template <> int countl_zero(ull x) { return __builtin_clzll(x); }
template <typename T> int countr_zero(T x); template <> int countr_zero(uint x) { return __builtin_ctz(x); } template <> int countr_zero(ull x) { return __builtin_ctzll(x); }
template <typename T> int bit_width(T x) { return numeric_limits<T>::digits - countl_zero(x); }
#endif

template <typename T> int sgn(T x) { return (T(0) < x) - (x < T(0)); }
template <typename T> T randint(T l, T r) { return uniform_int_distribution<T>(l, r)(rng); }
template <typename T> T randf(T l, T r) { return uniform_real_distribution<T>(l, r)(rng); }
template <typename T> int log2if(T x) { return bit_width(x + 0ULL) - 1; }
template <typename T> int log2ic(T x) { return bit_width(x - 1ULL); }
bool inside(int x, int y, int n, int m) { return x >= 0 && x < n && y >= 0 && y < m; }
ll sqdist(const pair<int, int> &p, const pair<int, int> &q) { ll x = p.first - q.first, y = p.second - q.second; return x * x + y * y; }

template <typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<>>;
template <typename T, typename Comp = less<>> using ordered_set = tree<T, null_type, Comp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T = null_type> using pref_trie = trie<string, T, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;

#if __cplusplus >= 201703L
template <typename, typename = void> struct is_iterable : false_type {};
template <typename T> struct is_iterable<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> : true_type {};
template <> struct is_iterable<string> : false_type {};
template <typename T> constexpr bool is_iterable_v = is_iterable<T>::value;
template <typename T, typename V = enable_if_t<is_iterable_v<T>, typename T::value_type>> ostream &operator<<(ostream &os, const T &t) { for (const V &v : t) os << v << ' '; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << '(' << p.first << ' ' << p.second << ')'; }
void dbg_header_(const char *f, int l, const char *e) { cout << "\033[35m(" << f << ':' << l << ") \033[1m" << e << ":\033[0m "; }
template <typename T, typename = enable_if_t<!is_iterable_v<T>>> void dbg_(const T &t, const char *f, int l, const char *e) { dbg_header_(f, l, e); cout << "\033[33;1m" << t << "\033[0m" << endl; }
template <typename T, typename V = enable_if_t<is_iterable_v<T> && !is_iterable_v<typename T::value_type>, typename T::value_type>, typename = void> void dbg_(const T &t, const char *f, int l, const char *e) { dbg_header_(f, l, e); cout << "\033[33;1m"; for (const V &v : t) cout << v << ' '; cout << "\033[0m" << endl; }
template <typename T, typename = enable_if_t<is_iterable_v<T> && is_iterable_v<typename T::value_type>, typename T::value_type>, typename = void, typename = void> void dbg_(const T &t, const char *f, int l, const char *e) { dbg_header_(f, l, e); cout << '\n'; for (int i = 0; i < t.size(); i++) cout << "\033[36m" << i << ":\033[33;1m " << t[i] << "\033[0m" << endl; }
#ifdef DEBUG
#define dbg(t) dbg_((t), __func__, __LINE__, #t)
#else
#define dbg(t)
#endif
#endif
// clang-format on

template <typename T>
class HashSeq64
{
public:
    explicit HashSeq64(const T &s) : HashSeq64(s, rand_base()) {}

    HashSeq64(const T &s, ull b) : s(s), b(b), p(s.size() + 1), e(s.size() + 1)
    {
        e[0] = 1;
        for (int i = 0; i < s.size(); i++)
        {
            p[i + 1] = mul(p[i], b) + s[i];
            e[i + 1] = mul(e[i], b);
        }
    }

    ull hash(int l, int r) const { return (p[r] - mul(p[l], e[r - l]) + M) % M; }
    template <typename U> void push(const U &c) { s.push_back(c), p.push_back((mul(p.back(), b) + c) % M), e.push_back(mul(e.back(), b)); }
    void pop(int a = 1) { s.resize(s.size() - a), p.resize(p.size() - a), e.resize(e.size() - a); }
    int size() const { return s.size(); }
    static ull rand_base() { return randint<ull>(69, M - 1); }

    T s;
    ull b;
    constexpr static ull M = (1ULL << 61) - 1;

private:
    static ull mul(ull a, ull b)
    {
        ull l1 = uint(a), h1 = a >> 32, l2 = uint(b), h2 = b >> 32;
        ull l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
        ull ans = (l & M) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
        ans = (ans & M) + (ans >> 61);
        ans = (ans & M) + (ans >> 61);
        return ans - 1;
    }

    vector<ull> p;
    vector<ull> e;
};

void solve()
{
#ifdef DEBUG
    cout << "\033[31;1m======================================================================\033[0m" << endl;
#endif
    int n, m;
    cin >> n >> m;
    vector grid(n * 2, vector<char>(m * 2));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> grid[i][j];
            grid[i + n][j] = grid[i][j + m] = grid[i + n][j + m] = grid[i][j];
        }
    }
    ull base = HashSeq64<vector<char>>::rand_base();
    vector<HashSeq64<vector<char>>> hs;
    for (int i = 0; i < n * 2; i++)
        hs.emplace_back(grid[i], base);
    vector hcols(m, vector<ull>(n * 2));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n * 2; j++)
            hcols[i][j] = hs[j].hash(i, i + m);
    }
    vector<HashSeq64<vector<ull>>> hh;
    for (int i = 0; i < m; i++)
        hh.emplace_back(hcols[i], base);
    int bx = 0, by = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int l = 0, r = n - 1;
            int row = -1;
            while (l <= r)
            {
                int mid = l + (r - l) / 2;
                if (hh[j].hash(i, i + mid + 1) != hh[by].hash(bx, bx + mid + 1))
                {
                    row = mid;
                    r = mid - 1;
                }
                else
                {
                    l = mid + 1;
                }
            }
            if (row == -1)
                continue;
            l = 0, r = m - 1;
            int col = -1;
            while (l <= r)
            {
                int mid = l + (r - l) / 2;
                if (hs[i + row].hash(j, j + mid + 1) != hs[bx + row].hash(by, by + mid + 1))
                {
                    col = mid;
                    r = mid - 1;
                }
                else
                {
                    l = mid + 1;
                }
            }
            assert(col != -1);
            if (grid[i + row][j + col] < grid[bx + row][by + col])
            {
                bx = i;
                by = j;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << grid[bx + i][by + j];
        cout << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60