Submission #378957

#	Time	Username	Problem	Language	Result	Execution time	Memory
378957		ne4eHbKa	Sateliti (COCI20_satellti)	C++17	50 / 110	3071 ms	21196 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

int n, m;
const int N = 1e3 + 5;
const int NN = 2e3 + 5;

bool s[NN][NN];
int h[NN][NN], pw[NN], mpw[NN], x, y;

int subh(int i, int j, int n, int m) {
    using namespace MD;
    int res = h[i + n][j + m];
    sub(res, h[i][j + m]);
    sub(res, h[i + n][j]);
    add(res, h[i][j]);
    return prod(res, prod(pw[NN - 1 - j], mpw[NN - 1 - i]));
}

void upd(int i, int j) {
    if(subh(i, j, n, m) == subh(x, y, n, m)) return;
    int l = 0, r = n - 1;
    while(l < r) {
        int mid = l + r >> 1;
        subh(x, y, mid + 1, m) ==
        subh(i, j, mid + 1, m)
            ? l = mid + 1
            : r = mid;
    }
    int I = l;
    l = 0, r = m - 1;
    while(l < r) {
        int mid = l + r >> 1;
        subh(x, y, I + 1, mid + 1) ==
        subh(i, j, I + 1, mid + 1)
            ? l = mid + 1
            : r = mid;
    }
    int J = l;
    for(int pi = 0; pi < I; ++pi)
        for(int pj = 0; pj < m; ++pj)
            assert(s[i + pi][j + pj] == s[x + pi][y + pj]);
    for(int pj = 0; pj < J; ++pj)
        assert(s[i + I][j + pj] == s[x + I][y + pj]);
    assert(s[i + I][j + J] != s[x + I][y + J]);
    if(s[i + I][j + J] < s[x + I][y + J])
        x = i, y = j;
}

void solve() {
    using namespace MD;
    cin >> n >> m;
    for(int i = 0; i < NN; ++i)
        pw[i] = i ? prod(pw[i - 1], 2) : 1;
    for(int i = 0; i < NN; ++i)
        mpw[i] = i ? prod(mpw[i - 1], pw[m]) : 1;
    for(int i = 0; i < n + n; ++i) {
        for(int j = 0; j < m + m; ++j) {
            if(i < n && j < m) {
                char c; cin >> c;
                s[i][j] = c == '.';
            } else s[i][j] = s[i % n][j % m];
            h[i + 1][j + 1] = prod(pw[j], prod(s[i][j], mpw[i]));
            add(h[i + 1][j + 1], h[i][j + 1]);
            add(h[i + 1][j + 1], h[i + 1][j]);
            sub(h[i + 1][j + 1], h[i][j]);
        }
    }
    x = y = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(i || j) upd(i, j);
    for(int i = 0; i < n; ++i, cout << '\n')
        for(int j = 0; j < m; ++j)
            cout << (s[i + x][j + y] ? '.' : '*');
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void upd(int, int)':
Main.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = l + r >> 1;
      |                   ~~^~~

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