oj.uz

Submission #1078639

# Submission time Handle Problem Language Result Execution time Memory
1078639 2024-08-28T02:16:50 Z Neco_arc Sateliti (COCI20_satellti) C++17
10 / 110
 27 ms 10848 KB 
#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Sateliti"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e3 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n, m, N, M;
char a[maxn][maxn];
ll H[maxn][maxn], po[maxn * maxn];
ll Hash[maxn][maxn];

pair<int, int> nex(int x, int y, int len) {
    int k = len / M;
    if(len % M == 0) return {x + k - 1, y + M - 1};
    return {x + k, y + (len % M) - 1};
}

ll getR(int x, int l, int r) {
    if(l > r) return 0;
    return Hash[x][r] - Hash[x][l - 1] * po[r - l + 1];
}

ll get(int u, int v, int len) {
    ll ans = 0;
    int k = len / M;
    if(k) ans = H[u + k - 1][v] - H[u - 1][v] * po[k * M];
    ans = ans * po[len % M] + getR(u + k, v, v + (len % M) - 1);

    return ans;
}

int check(int x, int y, int u, int v) {
    int l = 1, r = N * M - 1;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(get(x, y, mid) == get(u, v, mid)) l = mid + 1;
        else r = mid - 1;
    }

    tie(x, y) = nex(x, y, r + 1), tie(u, v) = nex(u, v, r + 1);
    return a[u][v] < a[x][y];
}

ll HASH(string s) {
    ll ans = 0;
    for(char c : s) ans = ans * base + c;
    return ans;
}

void solve()
{

    cin >> n >> m;
    N = n, M = m;

    fi(i, 1, n) fi(j, 1, m) {
        cin >> a[i][j];
        a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
    }

    n *= 2, m *= 2;

    fi(i, 1, n) {
        fi(j, 1, m) Hash[i][j] = Hash[i][j - 1] * base + a[i][j];
        fi(j, 1, m - M + 1) H[i][j] = H[i - 1][j] * po[M] + getR(i, j, j + M - 1);
    }

    pair<int, int> ans = {1, 1};
    fi(i, 1, N) fi(j, 1, M) {
        if(check(ans.first, ans.second, i, j)) ans = {i, j};
    }

    int u, v; tie(u, v) = ans;
    fi(i, 1, N) fi(j, 1, M) {
        cout << a[u + i - 1][v + j - 1];
        if(j == M) cout << '\n';
    }

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }

    po[0] = 1;
    fi(i, 1, maxn * maxn) po[i] = po[i - 1] * base;

    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:33: warning: iteration 16006 invokes undefined behavior [-Waggressive-loop-optimizations]
  111 |     fi(i, 1, maxn * maxn) po[i] = po[i - 1] * base;
      |                           ~~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:14:38: note: within this loop
   14 | #define fi(i, a, b) for(int i = a; i <= b; i++)
      |                                      ^
Main.cpp:111:5: note: in expansion of macro 'fi'
  111 |     fi(i, 1, maxn * maxn) po[i] = po[i - 1] * base;
      |     ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 2 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 2 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 22 ms 10848 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 19 ms 10624 KB Output is correct
12 Incorrect 27 ms 10652 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 2 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 22 ms 10848 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 19 ms 10624 KB Output is correct
12 Incorrect 27 ms 10652 KB Output isn't correct
13 Halted 0 ms 0 KB -