oj.uz

Submission #377475

# Submission time Handle Problem Language Result Execution time Memory
377475 2021-03-14T09:00:21 Z kartel Sateliti (COCI20_satellti) C++14
10 / 110
 261 ms 13292 KB 
#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;
        }
    }

    if (L == n && r == m) {
        return;
    }

//    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1388 KB Output is correct
2 Correct 7 ms 1260 KB Output is correct
3 Correct 8 ms 1260 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 7 ms 1388 KB Output is correct
6 Correct 7 ms 1388 KB Output is correct
7 Correct 8 ms 1388 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1388 KB Output is correct
2 Correct 7 ms 1260 KB Output is correct
3 Correct 8 ms 1260 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 7 ms 1388 KB Output is correct
6 Correct 7 ms 1388 KB Output is correct
7 Correct 8 ms 1388 KB Output is correct
8 Correct 261 ms 13292 KB Output is correct
9 Correct 10 ms 748 KB Output is correct
10 Incorrect 4 ms 5228 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1388 KB Output is correct
2 Correct 7 ms 1260 KB Output is correct
3 Correct 8 ms 1260 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 7 ms 1388 KB Output is correct
6 Correct 7 ms 1388 KB Output is correct
7 Correct 8 ms 1388 KB Output is correct
8 Correct 261 ms 13292 KB Output is correct
9 Correct 10 ms 748 KB Output is correct
10 Incorrect 4 ms 5228 KB Output isn't correct
11 Halted 0 ms 0 KB -