oj.uz

Submission #248505

# Submission time Handle Problem Language Result Execution time Memory
248505 2020-07-12T14:41:11 Z Vladikus004 Osmosmjerka (COCI17_osmosmjerka) C++14
140 / 160
 1053 ms 262148 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma target("tune=native")
//#define int long long
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 500, P[2] = {31, 10}, mod[2] = {1000000000 + 7, 999999937};
int n, m, k;
string s[N];
ll hs[N][N][31][8][2], deg[31][2];

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void make_hash(){
    deg[0][0] = deg[0][1] = 1;
    deg[1][0] = P[0]; deg[1][1] = P[1];
    for (int i = 2; i < 31; i++) {
        deg[i][0] = deg[i - 1][0] * deg[i - 1][0];
        deg[i][1] = deg[i - 1][1] * deg[i - 1][1];
        deg[i][0] %= mod[0];
        deg[i][1] %= mod[1];
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < 8; k++)
            hs[i][j][0][k][0] = hs[i][j][0][k][1] = (s[i][j] - 'a' + 1);
    for (int st = 1; st < 31; st++){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                for (int k = 0; k < 8; k++){
                    hs[i][j][st][k][0] = hs[((i+(dx[k]*(1<<(st - 1)))%n)+2*n)%n][((j+(dy[k]*(1<<(st - 1)))%m)+2*m)%m][st - 1][k][0] * deg[st][0] + hs[i][j][st - 1][k][0];
                    hs[i][j][st][k][1] = hs[((i+(dx[k]*(1<<(st - 1)))%n)+2*n)%n][((j+(dy[k]*(1<<(st - 1)))%m)+2*m)%m][st - 1][k][1] * deg[st][1] + hs[i][j][st - 1][k][1];
                    hs[i][j][st][k][0] %= mod[0];
                    hs[i][j][st][k][1] %= mod[1];
                }
            }
        }
    }
}

map <pair<ll, ll>, ll> mp;
void get_cnt(int k){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            for (int d = 0; d < 8; d++){
                pair <ll, ll> e;
                int X = i, Y = j;
                for (int g = 0; g < 31; g++){
                    if (!((1<<g) & k)) continue;
                    e.first += hs[X][Y][g][d][0] * deg[g][0];
                    e.second += hs[X][Y][g][d][1] * deg[g][1];
                    e.first %= mod[0];
                    e.second %= mod[1];
                    X = ((X+(dx[d]*(1<<g))%n)+2*n)%n;
                    Y = ((Y+(dy[d]*(1<<g))%m)+2*m)%m;
                }
                mp[e]++;
            }
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) cin >> s[i];
    make_hash();
    get_cnt(k);
    ll ans = 0;
    for (auto u: mp){
        ans += u.second * u.second;
//        cout << u.first.second << " : " << u.second << "\n";
    }
    ll zn = n * m * 8; zn *= zn;
    ll gcd = __gcd(ans, zn);
    cout << ans/gcd << "/"<<zn/gcd;
}

Compilation message

osmosmjerka.cpp:4:0: warning: ignoring #pragma target  [-Wunknown-pragmas]
 #pragma target("tune=native")

Subtask #1
140.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 3 ms 2176 KB Output is correct
5 Correct 10 ms 7040 KB Output is correct
6 Correct 72 ms 35192 KB Output is correct
7 Correct 1053 ms 254200 KB Output is correct
8 Runtime error 107 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)