Submission #244946

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
244946	2020-07-05T09:51:54 Z	VEGAnn	Osmosmjerka (COCI17_osmosmjerka)	C++14	140 / 160	4000 ms	26248 KB

osmosmjerka

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define s2 array<short,2>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 510;
const int M = 100100;
const int x = 233;
const int PW = 233;
const int md = 999999937;
//const int md = 998244353;
//const int md = 988244353;
//const int md = int(1e9) + 9;
//const int md = int(1e9) + 7;
gp_hash_table<int, int> mem;
int n, m, stp[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
int hsh[N], xn, a[N][N], big_x, k, po[N * N], lcm, pre[8][N][N], inv;
s2 nt[8][N][N];

int mult(int x, int y) { return (1ll * x * y) % md; }

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int sub(int x, int y){
    x -= y;
    if (x < 0)
        x += md;
    return x;
}

int binpow(int x, int po){
    int res = 1;
    while (po > 0){
        if (x & 1)
            res = mult(res, x);
        x = mult(x, x);
        po >>= 1;
    }
    return res;
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m >> k;

    lcm = n * m / __gcd(n, m);

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        char c; cin >> c;

        a[i][j] = c - 'a' + 1;
    }

    po[0] = 1;

    for (int i = 1; i <= lcm; i++)
        po[i] = mult(po[i - 1], x);

    big_x = binpow(po[lcm], k / lcm);
    inv = binpow(sub(po[lcm], 1), md - 2);

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    for (int it = 0; it < 8; it++){
        int x = i, y = j;

        hsh[0] = 0;

        for (int len = 1; len <= n; len++) {
            hsh[len] = sum(hsh[len - 1], mult(po[len - 1], a[x][y]));

            x += stp[it][0];
            y += stp[it][1];

            if (x < 0) x += n;
            if (y < 0) y += m;
            if (x >= n) x -= n;
            if (y >= m) y -= m;
        }

        pre[it][i][j] = hsh[n];
        nt[it][i][j] = {x, y};
    }

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    for (int it = 0; it < 8; it++){
        int x = i, y = j;

        int ost = k % lcm, mul = 1, hs = 0, ost_hsh = 0;

        for (int lst = lcm / n; lst > 0; lst--){
            int cur = mult(mul, pre[it][x][y]);

            hs = sum(hs, cur);
            mul = mult(mul, po[n]);

            if (ost > 0){
                if (ost < n){
                    int xx = x, yy = y, mlu = mul;

                    while (ost > 0){
                        ost_hsh = sum(ost_hsh, mult(mlu, a[xx][yy]));
                        mlu = mult(mlu, PW);

                        xx += stp[it][0];
                        yy += stp[it][1];

                        if (xx < 0) xx += n;
                        if (yy < 0) yy += m;
                        if (xx >= n) xx -= n;
                        if (yy >= m) yy -= m;

                        ost--;
                    }
                } else {
                    ost -= n;
                    ost_hsh = sum(ost_hsh, cur);
                }
            }

            s2 nw = nt[it][x][y];

            x = nw[0];
            y = nw[1];
        }

        int cnt = k / lcm, rhsh = 0;

        if (cnt > 0){
            rhsh = mult(hs, sub(big_x, 1));
            rhsh = mult(rhsh, inv);
        }

        rhsh = sum(rhsh, mult(big_x, ost_hsh));

        mem[rhsh]++;
    }

    ll res = 0;

    for (auto cr : mem){
        ll nw = cr.second;

        nw *= nw;

        res += nw;
    }

    ll full = ll(n) * ll(m) * ll(n) * ll(m) * ll(8) * ll(8);
    ll gc = __gcd(full, res);

    cout << res / gc << "/" << full / gc;

    return 0;
}

Compilation message

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:96:29: warning: narrowing conversion of 'x' from 'int' to 'short int' inside { } [-Wnarrowing]
         nt[it][i][j] = {x, y};
                             ^
osmosmjerka.cpp:96:29: warning: narrowing conversion of 'y' from 'int' to 'short int' inside { } [-Wnarrowing]

Subtask #1

140.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	512 KB	Output is correct
2	Correct	5 ms	640 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	5 ms	1152 KB	Output is correct
5	Correct	10 ms	2048 KB	Output is correct
6	Correct	138 ms	6380 KB	Output is correct
7	Correct	1727 ms	26248 KB	Output is correct
8	Execution timed out	4082 ms	12372 KB	Time limit exceeded