oj.uz

Submission #96800

# Submission time Handle Problem Language Result Execution time Memory
96800 2019-02-12T03:55:38 Z tieunhi Osmosmjerka (COCI17_osmosmjerka) C++14
100 / 160
 4000 ms 29368 KB 
#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
100.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Incorrect 35 ms 1756 KB Output isn't correct
7 Incorrect 685 ms 8684 KB Output isn't correct
8 Execution timed out 4082 ms 29368 KB Time limit exceeded