Submission #713295

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713295	2023-03-21T16:27:06 Z	Johann	Osmosmjerka (COCI17_osmosmjerka)	C++14	140 / 160	4000 ms	87612 KB

osmosmjerka

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<pii> vpii;
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()

const ll MOD = ((1LL << 61) - 1);
const ll P = 9973;
const ll P1 = 98999;
const ll P2 = 22573;
const ll P3 = 1367;
const ll P4 = 41809;
ll mod_mul(ll a, ll b)
{
    __int128 res = (__int128)a * b;
    return res % MOD;
}

int N, M, K;
vpii dirs = {{1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
pii move(pii &pos, pii &dir, ll amount)
{
    pii ans;
    ans.first = (pos.first + dir.first * amount) % N;
    ans.second = (pos.second + dir.second * amount) % M;
    ans.first = (ans.first + N) % N;
    ans.second = (ans.second + M) % M;
    assert(0 <= ans.first && 0 <= ans.second && ans.first < N && ans.second < M);
    return ans;
}
vvi grid;
vvvi dp;
vi pot;

void initDP(int d)
{
    int logheight = ceil(log2(K) + 1);
    dp.assign(N, vvi(M, vi(logheight, 0)));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            dp[i][j][0] = grid[i][j];

    pot.assign(logheight, P); // pot[i] = P^(2^i)
    for (int l = 1; l < logheight; ++l)
    {
        pot[l] = mod_mul(pot[l - 1], pot[l - 1]);
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
            {
                pii coords = {i, j};
                ll in, jn;

                tie(in, jn) = move(coords, dirs[d], 1LL << (l - 1));
                dp[i][j][l] = (dp[i][j][l - 1] + mod_mul(pot[l - 1], dp[in][jn][l - 1])) % MOD;
                assert(dp[i][j][l] >= 0);
            }
    }
}

ll lift(pii pos, int d, int k)
{
    int i, j;
    tie(i, j) = pos;
    ll ans = 0;
    ll pp = 1;
    for (int l = 0; l < sz(dp[i][j]); ++l)
    {
        if (k & (1 << l))
        {
            ans = (ans + mod_mul(pp, dp[i][j][l])) % MOD;
            pp = mod_mul(pp, pot[l]);
            tie(i, j) = move(pos, dirs[d], 1LL << l);
        }
        assert(ans >= 0);
    }
    return ans;
}

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

    cin >> N >> M >> K;

    grid.assign(N, vi(M, 0));
    for (int i = 0; i < N; ++i)
    {
        string tmp;
        cin >> tmp;
        for (int j = 0; j < M; ++j)
            grid[i][j] = tmp[j];
    }

    vi paths;
    for (int d = 0; d < sz(dirs); ++d)
    {
        initDP(d);
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                paths.push_back(lift({i, j}, d, K));
    }
    sort(all(paths));

    ll num = 0;
    ll denom = sz(paths) * sz(paths);

    ll last = paths.front();
    ll cnt = 1;
    for (int i = 1; i < sz(paths); ++i)
    {
        if (paths[i] == last)
            ++cnt;
        else
        {
            num += cnt * cnt;
            cnt = 1;
            last = paths[i];
        }
    }
    num += cnt * cnt;

    ll g = __gcd(num, denom);

    cout << num / g << "/" << denom / g << endl;

    return 0;
}

Subtask #1

140.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	4 ms	340 KB	Output is correct
5	Correct	17 ms	884 KB	Output is correct
6	Correct	102 ms	2860 KB	Output is correct
7	Correct	1111 ms	20584 KB	Output is correct
8	Execution timed out	4074 ms	87612 KB	Time limit exceeded