oj.uz

Submission #443545

# Submission time Handle Problem Language Result Execution time Memory
443545 2021-07-10T17:52:32 Z nhuang685 Osmosmjerka (COCI17_osmosmjerka) C++17
100 / 160
 4000 ms 10368 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const ll P = 9973;
const ll MOD = 1e9 + 9;

int M, N, K;
string grid[500];
unordered_map<ll, ll> cnt;
vector<int> dx, dy;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    // freopen("input.txt", "r", stdin);
    cin >> M >> N >> K;
    K = min(lcm(M, N), K);

    dx = {M - 1, M - 1, 0, 1, 1, 1, 0, M - 1};
    dy = {0, 1, 1, 1, 0, N - 1, N - 1, N - 1};

    for (int i = 0; i < M; ++i) cin >> grid[i];

    ll num = 0;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int d = 0; d < 8; ++d) {
                int x = i;
                int y = j;
                ll ppow = 1;
                ll hash_val = 0;

                for (int k = 0; k < K; ++k) {
                    hash_val = (hash_val + (grid[x][y] - 'a' + 1) * ppow) % MOD;
                    ppow = (ppow * P) % MOD;
                    x = (x + dx[d]) % M;
                    y = (y + dy[d]) % N;
                }
                cnt[hash_val]++;
                num++;
            }
        }
    }

    ll numerator = 0;
    ll denominator = num * num;
    for (auto i : cnt) {
        numerator += i.second * i.second;
    }

    ll g = gcd(numerator, denominator);
    cout << numerator / g << "/" << denominator / g << '\n';
}

Subtask #1
100.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Execution timed out 4041 ms 1676 KB Time limit exceeded
7 Execution timed out 4027 ms 700 KB Time limit exceeded
8 Execution timed out 4080 ms 10368 KB Time limit exceeded