oj.uz

Submission #701413

# Submission time Handle Problem Language Result Execution time Memory
701413 2023-02-21T08:07:23 Z PixelCat Sateliti (COCI20_satellti) C++14
10 / 110
 172 ms 4668 KB 
/* nya */
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")

#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

namespace {

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(int k, 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];
    }
    for(int len = 1; len < k; 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];
    }
}

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

#ifdef NYAOWO
void timer(bool out, string name = "(timer)") {
    static long long last = -1;
    auto now = clock();
    if(last != -1 && out) {
        cerr << fixed << setprecision(5);
        cerr << name << ": " << (double)(now - last) / CLOCKS_PER_SEC << "\n";
    }
    last = now;
}
#else
#define timer(...)
#endif

inline void in(int &x) {
    x = 0;
    for(char ch; (ch = getchar()) <= '9' && ch >= '0';)
        x = x * 10 + ch - '0';
}

}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // OAO
    timer(0);
    in(n); in(m);
    For(i, 0, n - 1) For(j, 0, m - 1) {
        char ch; ch = getchar();
        val[i][j] = (ch == '.');
        g[i][j] = ch;
        if(j == m - 1) ch = getchar();
    }
    
    getSA(m, nxt1);
    // timer(1, "SA 1");
    
    For(i, 0, n - 1) For(j, 0, m - 1) {
        auto id = p2i(i, j);
        val[i][j] = rk[id];
    }

    // timer(0);
    getSA(n, nxt2);
    // timer(1, "SA 2");
    
    auto p = i2p(sa[0]);
    int x = p.F, y = p.S;
    For(i, x, x + n - 1) {
        For(j, y, y + m - 1) {
            putchar(g[i - (i >= n) * n][j - (j >= m) * m]);
        }
        putchar('\n');
    }
    timer(1);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 2 ms 976 KB Output is correct
7 Correct 4 ms 980 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 2 ms 976 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 119 ms 4552 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 172 ms 4552 KB Output is correct
12 Incorrect 172 ms 4668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 2 ms 976 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 119 ms 4552 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 172 ms 4552 KB Output is correct
12 Incorrect 172 ms 4668 KB Output isn't correct
13 Halted 0 ms 0 KB -