Submission #96798

#	Time	Username	Problem	Language	Result	Execution time	Memory
96798		tieunhi	Osmosmjerka (COCI17_osmosmjerka)	C++14	0 / 160	4051 ms	29788 KiB

osmosmjerka

#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define pii pair<int, int>
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define N 505
#define BASE 97
#define mod 1000000007
#define mid (r + l)/2

using namespace std;

int n, m, k;
ll res;
char c[N][N];
map<ll, int> ma;
int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    //freopen("OUT.TXT", "w", stdout);
    cin >> n >> m >> k;
    k = min(k, max(n, m));
    FOR(i, 1, n)
        FOR(j, 1, m) cin >> c[i][j];
    FOR(i, 1, n)
        FOR(j, 1, m)
            FOR(dir, 0, 7)
            {
                ll val = 0;
                int x = i, y = j;
                FOR(step, 1, k)
                {
                    val = val*BASE + (c[x][y] - 'a');
                    x += fx[dir];
                    y += fy[dir];
                    if (x > n) x -= n;
                    if (x < 1) x += n;
                    if (y > m) y -= m;
                    if (y < 1) y += m;
                }
                int tt = ma[val];
                res -= 1ll*tt*tt;
                tt++;
                res += 1ll*tt*tt;
                ma[val] = tt;
            }
    ll MS = 64ll*n*n*m*m;
    ll gcd = __gcd(res, MS);
    cout <<res/gcd;
    cout <<'\\';
    cout <<MS/gcd;
}

• Subtask 1: 0 / 160