Submission #244979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
244979	2020-07-05T10:36:01 Z	VEGAnn	Osmosmjerka (COCI17_osmosmjerka)	C++14	80 / 160	489 ms	25232 KB

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 = 233;
const int md = 999999937;
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];

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 = x, 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];
            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];
        }

        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)
                    rhsh[i][j] = sum(rhsh[i][j], mult(mul, nw));
            }

            if (kk & 1)
                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

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

Subtask #1

80.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	384 KB	Output isn't correct
2	Incorrect	5 ms	384 KB	Output isn't correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	5 ms	640 KB	Output is correct
5	Correct	7 ms	1024 KB	Output is correct
6	Correct	23 ms	4088 KB	Output is correct
7	Incorrect	148 ms	21464 KB	Output isn't correct
8	Incorrect	489 ms	25232 KB	Output isn't correct