Submission #377523

#	Time	Username	Problem	Language	Result	Execution time	Memory
377523		ne4eHbKa	Sateliti (COCI20_satellti)	C++17	50 / 110	3089 ms	172524 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;}
};

const int N = 1e3 + 5;
const int NN = 2e3 + 5;
const int K = 4e6 + 5;
const int B = 9;
const int W = 1 << B;

int n, m, nn, mm, d;
int a[NN][NN], b[NN][NN], A[NN][NN], z[NN][NN];
int fst[K], lst[K], nxt[K], vl[K], t, e[K], ne;

inline void add(const int &i, const int &j) {
    umax(d, i + 1);
    if(fst[i] < 0) {
        fst[i] = lst[i] = t;
    } else {
        nxt[lst[i]] = t;
        lst[i] = t;
    }
    vl[t++] = j;
}

inline void iterate(const int &i) {
    if(fst[i] < 0) return;
    for(int j = fst[i]; ; j = nxt[j]) {
        e[ne++] = vl[j];
        if(j == lst[i]) {
            fst[i] = -1;
            return;
        }
    }
}

typedef pair<pii, pii> ppp;
ppp f[K]; int nf;

void combine(int a[NN][NN], int b[NN][NN], int c[NN][NN], int dx, int dy) {
    nf = 0;
    for(int i = 0; i + dx < nn; ++i)
        for(int j = 0; j + dy < mm; ++j)
            f[nf++] = {{a[i][j], b[i + dx][j + dy]}, {i, j}};

    d = t = 0;
    for(int i = 0; i < nf; ++i)
        add(f[i].ft.sd & W - 1, i);
    ne = 0;
    for(int i = 0; i < d; ++i)
        iterate(i);

    d = t = 0;
    for(int i = 0; i < ne; ++i)
        add(f[e[i]].ft.sd >> B, e[i]);
    ne = 0;
    for(int i = 0; i < d; ++i)
        iterate(i);

    d = t = 0;
    for(int i = 0; i < ne; ++i)
        add(f[e[i]].ft.ft & W - 1, e[i]);
    ne = 0;
    for(int i = 0; i < d; ++i)
        iterate(i);

    d = t = 0;
    for(int i = 0; i < ne; ++i)
        add(f[e[i]].ft.ft >> B, e[i]);
    ne = 0;
    for(int i = 0; i < d; ++i)
        iterate(i);

    for(int i = 0, j = 0; i < nf; ++i) {
        auto &g = f[e[i]];
        if(i && g.ft != f[e[i - 1]].ft)
            ++j;
        c[g.sd.ft][g.sd.sd] = j;
    }
}

void solve() {
    memset(fst, -1, sizeof fst);
    cin >> n >> m;
    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;
                a[i][j] = c == '.';
            } else
                a[i][j] = a[i % n][j % m];
        }
    }
    memset(A, 0, sizeof A);
    memcpy(z, a, sizeof z);
    nn = n << 1;
    mm = m << 1;
    for(int i = 0, u = m; ; ++i) {
        if(i) combine(a, a, a, 0, 1 << i - 1);
        if(u & 1 << i) {
            combine(a, A, A, 0, 1 << i);
            u ^= 1 << i;
            if(!u) break;
        }
    }
    memcpy(a, A, sizeof A);
    memset(A, 0, sizeof A);
    for(int i = 0, u = n; ; ++i) {
        if(i) combine(a, a, a, 1 << i - 1, 0);
        if(u & 1 << i) {
            combine(a, A, A, 1 << i, 0);
            u ^= 1 << i;
            if(!u) break;
        }
    }
    int x = 0, y = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(A[i][j] < A[x][y])
                x = i, y = j;
    for(int i = 0; i < n; ++i, cout << '\n')
        for(int j = 0; j < m; ++j) cout << (z[x + i][y + j] ? '.' : '*');
}

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 combine(int (*)[2005], int (*)[2005], int (*)[2005], int, int)':
Main.cpp:73:28: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   73 |         add(f[i].ft.sd & W - 1, i);
      |                          ~~^~~
Main.cpp:87:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   87 |         add(f[e[i]].ft.ft & W - 1, e[i]);
      |                             ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:124:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  124 |         if(i) combine(a, a, a, 0, 1 << i - 1);
      |                                        ~~^~~
Main.cpp:134:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  134 |         if(i) combine(a, a, a, 1 << i - 1, 0);
      |                                     ~~^~~

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