Submission #244891

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
244891	2020-07-05T08:46:57 Z	VEGAnn	Osmosmjerka (COCI17_osmosmjerka)	C++14	80 / 160	4000 ms	19992 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())
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 md = 998244353;
const int md = int(1e9) + 7;
gp_hash_table<int, int> mem;
ll res;
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];

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;
    }

    assert(n == m);

    po[0] = 1;

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

    big_x = binpow(po[n], k / n);

    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 += n;
            if (x >= n) x -= n;
            if (y >= n) y -= n;
        }

        int cnt = k / n, rhsh = 0;

        if (cnt > 0){
            rhsh = mult(hsh[n], sub(big_x, 1));
            rhsh = mult(rhsh, binpow(sub(po[n], 1), md - 2));
        }

        int ost = k % n;

        if (ost > 0)
            rhsh = sum(rhsh, mult(big_x, hsh[ost]));

        mem[rhsh]++;
    }

    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;
}

Subtask #1

80.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	5 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	512 KB	Output is correct
5	Correct	11 ms	640 KB	Output is correct
6	Runtime error	6 ms	1024 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	7 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Execution timed out	4090 ms	19992 KB	Time limit exceeded