Submission #244997

#	Time	Username	Problem	Language	Result	Execution time	Memory
244997		VEGAnn	Osmosmjerka (COCI17_osmosmjerka)	C++14	160 / 160	572 ms	25944 KiB

osmosmjerka

#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
#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 = 73;
const int md = 999999937;
//const int md = int(1e9) + 9;
//const int md = 998244353;
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 a[N][N], hsh[2][N][N], rhsh[N][N], k;
s2 nt[2][N][N], from[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;

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

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

    for (int it = 0; it < 8; it++){
        int tp = 0;

        int ad = PW, kk = k, mul = 1;

        for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            hsh[0][i][j] = a[i][j];
            from[i][j] = {i, j};
            rhsh[i][j] = 0;

            int x = i, y = j;

            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;

            nt[0][i][j] = {x, y};

            if (kk & 1) {
                rhsh[i][j] = hsh[0][i][j];
                from[i][j] = {x, y};
            }
        }

        if (kk & 1)
            mul = PW;

        kk >>= 1;

        while (kk > 0){
            for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                int x = nt[tp][i][j][0], y = nt[tp][i][j][1];

                int nw = sum(mult(hsh[tp][x][y], ad), hsh[tp][i][j]);

                hsh[tp ^ 1][i][j] = nw;

                nt[tp ^ 1][i][j] = nt[tp][x][y];
            }

            if (kk & 1) {
                for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++) {
                    int x = from[i][j][0], y = from[i][j][1];

                    int nw = hsh[tp ^ 1][x][y];

                    rhsh[i][j] = sum(rhsh[i][j], mult(mul, nw));
                    from[i][j] = nt[tp ^ 1][x][y];
                }

                mul = mult(mul, mult(ad, ad));
            }

            ad = mult(ad, ad);
            tp ^= 1;
            kk >>= 1;
        }

        for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            mem[rhsh[i][j]]++;
    }

    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 (stderr)

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:77:31: warning: narrowing conversion of 'i' from 'int' to 'short int' inside { } [-Wnarrowing]
             from[i][j] = {i, j};
                               ^
osmosmjerka.cpp:77:31: warning: narrowing conversion of 'j' from 'int' to 'short int' inside { } [-Wnarrowing]
osmosmjerka.cpp:90:32: warning: narrowing conversion of 'x' from 'int' to 'short int' inside { } [-Wnarrowing]
             nt[0][i][j] = {x, y};
                                ^
osmosmjerka.cpp:90:32: warning: narrowing conversion of 'y' from 'int' to 'short int' inside { } [-Wnarrowing]
osmosmjerka.cpp:94:35: warning: narrowing conversion of 'x' from 'int' to 'short int' inside { } [-Wnarrowing]
                 from[i][j] = {x, y};
                                   ^
osmosmjerka.cpp:94:35: warning: narrowing conversion of 'y' from 'int' to 'short int' inside { } [-Wnarrowing]

• Subtask 1: 160 / 160