Submission #1206372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206372		vux2code	Sateliti (COCI20_satellti)	C++20	110 / 110	208 ms	36676 KiB

Main

// Src : Vux2Code
/* Note :
    
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

#define fi first
#define se second

#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front

#define vec3d vector<vector<vector<ll>>>
#define vec2d vector<vector<ll>>
#define vec1d vector<ll>
vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}

template<typename T>
using rvs_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
#define foreach(i, j) for (ll i : (j))

#define all(a) (a).begin (), (a). end ()
#define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())

const ll maxN = 2e3 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;

void maxi(ll &x, ll y) { x = max(x, y); } 
void mini(ll &x, ll y) { x = min(x, y); }

/* ---------HASHING-------- */
const ll base1 = 3, base2 = 5;

/* ---------BITMASK-------- */
// ll count(ll x) { return __builtin_popcountll(x); }
// ll fst(ll x) { return 63 - __builtin_clzll(x); }
// ll last(ll x) { return __builtin_ctzll(x); }
// bool bit(ll x, ll y) { return ((x >> y) & 1); }

ll t = 1;

ll n, m, tmp, bs1 [maxN], bs2 [maxN], hs [maxN] [maxN];
char a [maxN] [maxN];

ll get (pll st, pll dis) {
    st = {st. fi - 1, st. se - 1};
    pll en = {st. fi + dis. fi, st. se + dis. se}; 
    return (hs [en. fi] [en. se]
         - hs [st. fi] [en. se] * bs1 [dis. fi]
         - hs [en. fi] [st. se] * bs2 [dis. se]
         + hs [st. fi] [st. se] * bs1 [dis. fi] * bs2 [dis. se]);
}

bool cmp (pll x, pll y) {
    pll last = {n, m};
    ll l, r, mid; 
    l = 1; r = n; 
    while (l <= r) {
        mid = (l + r) >> 1; 
        if (get (x, {mid, last. se}) != get (y, {mid, last. se})) {
            last. fi = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    l = 1; r = m;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (get (x, {last. fi, mid}) != get (y, {last. fi, mid})) {
            last. se = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    bool ans = (a [x. fi + last. fi - 1] [x. se + last. se - 1] == '*');
    // cerr << x. fi << ' ' << x. se << ' ' << y. fi << ' ' << y. se << ' ' << last. fi << ' ' << last. se << ' ' << ans << '\n';
    return ans;
}

void solve() {
    cin >> n >> m; 
    forinc (i, 1, n) forinc (j, 1, m) {
        cin >> a [i] [j];
        a [i + n] [j] = a [i] [j]; 
        a [i] [j + m] = a [i] [j]; 
        a [i + n] [j + m] = a [i] [j];
    }
    bs1 [0] = 1;
    forinc (i, 1, n) bs1 [i] = bs1 [i - 1] * base1;
    bs2 [0] = 1;
    forinc (i, 1, m) bs2 [i] = bs2 [i - 1] * base2; 
    forinc (i, 1, 2 * n) forinc (j, 1, 2 * m) {
        tmp = (a [i] [j] == '*' ? 1 : 2);
        hs [i] [j] = tmp
                     + hs [i - 1] [j] * base1
                     + hs [i] [j - 1] * base2
                     - hs [i - 1] [j - 1] * base1 * base2;
    }
    pll ans = {1, 1};
    forinc (i, 1, n) forinc (j, 1, m) if (cmp ({i, j}, ans)) ans = {i, j};
    forinc (i, ans. fi, ans. fi + n - 1) {
        forinc (j, ans. se, ans. se + m - 1) {
            cout << a [i] [j];
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // #define TASK "E:/Code/CP/task"
    // if (fopen (TASK".inp", "r")) {
    //     freopen (TASK".inp", "r", stdin);
    //     freopen (TASK".out", "w", stdout);
    // }
    // cin >> t;
    while (t--) solve();
}

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