Submission #701391

#	Time	Username	Problem	Language	Result	Execution time	Memory
701391		PixelCat	Sateliti (COCI20_satellti)	C++14	0 / 110	3 ms	980 KiB

Main

/* nya */
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int long long
#define INF (int)(1e18)
#define MOD (int)(1000000007)
// #define MOD (int)(998244353)
using namespace std;
using LL = long long;
using LLL = __int128_t;
using pii = pair<int, int>;

#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#endif

const int MAXN = 1024;

pii i2p(int id) {
    return pii(id >> 10, id & 1023);
}
int p2i(int a, int b) {
    return (a << 10) | b;
}

int n, m;
char g[MAXN][MAXN];
int val[MAXN][MAXN];

int sa[MAXN * MAXN];
int rk[MAXN * MAXN];
int tmp[MAXN * MAXN];

void getSA(function<int(int, int)> nxt) {
    int nm = n * m;
    int *r = rk;
    int *r2 = tmp;
    For(i, 0, n - 1) For(j, 0, m - 1) {
        sa[i * m + j] = p2i(i, j);
        r[p2i(i, j)] = val[i][j];
    }
    sort(sa, sa + nm, [&](int a, int b) {
        return r[a] < r[b];
    });
    for(int len = 1; len < 1024; len <<= 1) {
        auto cmp = [&](int a, int b) {
            if(r[a] != r[b]) return r[a] < r[b];
            a = nxt(a, len); b = nxt(b, len);
            return r[a] < r[b];
        };
        sort(sa, sa + nm, cmp);
        r2[sa[0]] = 0;
        For(i, 1, nm - 1) r2[sa[i]] = r2[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
        swap(r, r2);
    }
    if(r != rk) {
        For(i, 0, nm - 1) rk[i] = tmp[i];
    }
}

int nxt1(int id, int len) {
    pii p = i2p(id);
    return p2i(p.F, (p.S + len) % m);
}
int nxt2(int id, int len) {
    pii p = i2p(id);
    return p2i((p.F + len) % n, p.S);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // OAO
    cin >> n >> m;
    For(i, 0, n - 1) For(j, 0, m - 1) {
        char ch; cin >> ch;
        val[i][j] = (ch == '.');
        g[i][j] = ch;
    }
    getSA(nxt1);
    For(i, 0, n - 1) For(j, 0, m - 1) {
        auto id = p2i(i, j);
        val[i][j] = rk[id];
    }
    getSA(nxt1);
    auto p = i2p(sa[0]);
    int x = p.F, y = p.S;
    For(i, 0, n - 1) {
        For(j, 0, m - 1) cout << g[(x + i) % n][(y + j) % m];
        cout << "\n";
    }
    return 0;
}

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