Submission #1166415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166415		Owstin	Sateliti (COCI20_satellti)	C++20	0 / 110	1 ms	576 KiB

Main

#include <bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
class HashedString {
private:
    // change M and B if you want
    static const ll M = (1LL << 61) - 1;
    static const ll B;
    // pow[i] contains B^i % M
    static vector<ll> pow;
    // p_hash[i] is the hash of the first i characters of the given string
    vector<ll> p_hash;
    __int128 mul(ll a, ll b) { return (__int128)a * b; }
    ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
public:
    HashedString(const string &s) : p_hash(s.size() + 1) {
        while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
        p_hash[0] = 0;
        for (int i = 0; i < s.size(); i++) {
            p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
        }
    }
    ll get_hash(int start, int end) {
        ll raw_val = p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
        return (raw_val + M) % M;
    }
};
vector<ll> HashedString::pow = {1};
const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);

void solve() {
    int b, c; cin >> b >> c;
    vector<string> vec(2 * b);
    vector<HashedString> hashes;
    for (int i = 0; i < b; i++) {
        cin >> vec[i];
        vec[i] += vec[i];
        vec[i + b] += vec[i];
        hashes.pb(HashedString(vec[i]));
    }
    for (int i = 0; i < b; i++) {
        hashes.pb(HashedString(vec[i]));
    }
    pair<int, int> res = {b - 1, c - 1};
    vector<int> start(2 * c, b - 1);
    for (int i = b - 1; i < 2 * b; i++) {
        for (int j = c - 1; j < 2 * c; j++) {
            if (i < start[j]) {
                continue;
            }
            for (int k = b - 1; k >= 0; k--) {
                if (hashes[res.first - k].get_hash(res.second - c + 1, res.second) !=
                    hashes[i - k].get_hash(j - c + 1, j)) {
                    int lo = 0; int hi = c - 1;
                    while (lo < hi) {
                        int mid = (lo + hi) / 2;
                        if (hashes[res.first - k].get_hash(res.second - c + 1, res.second - c + 1 + mid) !=
                        hashes[i - k].get_hash(j - c + 1, j - c + 1 + mid)) {
                            hi = mid;
                        }
                        else {
                            lo = mid + 1;
                        }
                    }
                    if (vec[res.first - k][res.second - c + 1 + hi] == '*') {
                        for (int l = 0; l <= hi; l++) {
                            start[j + l] = max(start[j + l], i + b - k);
                        }
                    }
                    else {
                        res = {i, j};
                    }
                    break;
                }
            }
        }
    }
    for (int i = res.first - b + 1; i <= res.first; i++) {
        for (int j = res.second - c + 1; j <= res.second; j++) {
            cout << vec[i][j];
        }
        cout << endl;
    }
}
int main() {
    FAST_IO;
    //freopen("lightsout.in", "r", stdin);
    //freopen("lightsout.out", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}

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