Submission #377472

#	Time	Username	Problem	Language	Result	Execution time	Memory
377472		kartel	Sateliti (COCI20_satellti)	C++14	10 / 110	260 ms	13408 KiB

Main

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
//#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 2005;

int pr[N][N];
int invi[N * N], invj[N * N], pwi[N * N], pwj[N * N];
char c;
int a[N][N];
int n, m, I, J;

int mult(ll x, ll y) {return (x * y) % M;}
int sum(int x, int y) {x += y; if (x >= M) x -= M; return x;}
int mi(int x, int y) {x -= y; if (x < 0) x += M; return x;}

int bp(int x, int y) {
    if (!y) {
        return 1;
    }

    if (y & 1) {
        return mult(x, bp(x, y - 1));
    }

    int a = bp(x, y >> 1);

    return mult(a, a);
}

int get(int il, int jl, int ir, int jr) {
//    cerr << sum(mi(mi(pr[ir][jr], pr[il - 1][jr]), pr[ir][jl - 1]), pr[il - 1][jl - 1]) << el;
    return mult(invi[il - 1], mult(invj[jl - 1], sum(mi(mi(pr[ir][jr], pr[il - 1][jr]), pr[ir][jl - 1]), pr[il - 1][jl - 1])));
}

void upd(int i, int j) {
    int l = 1, r = n;

    while (l < r) {
        int md = (l + r + 1) >> 1;

        if (get(i, j, i + md - 1, j + m - 1) == get(I, J, I + md - 1, J + m - 1)) {
            l = md;
        }
        else {
            r = md - 1;
        }
    }

    int L = r;

    if (a[i + L - 1][j] != a[I + L - 1][J]) {
        if (a[i + L - 1][j] < a[I + L - 1][J]) {
            I = i;
            J = j;
        }
        return;
    }

    l = 1;
    r = m;
    while (l < r) {
        int md = (l + r + 1) >> 1;

        if (get(i + L - 1, j, i + L - 1, j + md - 1) == get(I + L - 1, J, I + L - 1, J + md - 1)) {
            l = md;
        }
        else {
            r = md - 1;
        }
    }

//    assert(r < m);

    if (a[i + L - 1][j + r] < a[I + L - 1][J + r]) {
        I = i;
        J = j;
    }
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n >> m;

    pwi[0] = pwj[0] = 1;
    invi[0] = invj[0] = 1;

    for (int i = 1; i <= 4 * n * m; i++) {
        pwi[i] = mult(pwi[i - 1], 7);
        invi[i] = bp(pwi[i], M - 2);

        pwj[i] = mult(pwj[i - 1], 11);
        invj[i] = bp(pwj[i], M - 2);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c;

            a[i][j] = (c == '.');
        }
    }

    for (int i = n + 1; i <= 2 * n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = a[i - n][j];
        }

        for (int j = m + 1; j <= 2 * m; j++) {
            a[i][j] = a[i - n][j - m];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = m + 1; j <= 2 * m; j++) {
            a[i][j] = a[i][j - m];
        }
    }

    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * m; j++) {
            pr[i][j] = sum(mi(sum(pr[i - 1][j], pr[i][j - 1]), pr[i - 1][j - 1]), mult(pwi[i - 1], mult(pwj[j - 1], a[i][j] + 1)));
        }
    }

    I = 1;
    J = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) {
                continue;
            }

            upd(i, j);
        }
    }

    for (int i = I; i <= I + n - 1; i++, cout << el) {
        for (int j = J; j <= J + m - 1; j++) {
            if (a[i][j]) {
                cout << '.';
            }
            else {
                cout << '*';
            }
        }
    }
}

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