oj.uz

Submission #370140

# Submission time Handle Problem Language Result Execution time Memory
370140 2021-02-23T11:41:25 Z Atill83 Osmosmjerka (COCI17_osmosmjerka) C++14
60 / 160
 179 ms 68716 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e3+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, m, k;
string s[MAXN];
int g[MAXN][MAXN];
const int base = 37;
map<int, int> mp;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int L = 30;
int par[MAXN][MAXN][L];
int basep[L];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>m>>k;

    for(int i = 0; i < n; i++){
        cin>>s[i];
        for(int j = 0; j < m; j++)
            g[i][j] = s[i][j] - 'a' + 1;
    }
    basep[0] = base;
    for(int i = 1; i < L; i++){
        basep[i] = 1LL * basep[i - 1] * basep[i - 1] % mod; 
    }

    for(int i = 0; i < 8; i++){
        dx[i] = (dx[i] + n) % n;
        dy[i] = (dy[i] + m) % m;
    }



    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            par[i][j][0] = g[i][j];
        }
    }
    for(int s = 0; s < 8; s++){

        for(int p = 1; p < L; p++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    int nx = (i + dx[s] * (1<<(p - 1)) % n) % n,
                        ny = (j + dy[s] * (1<<(p - 1)) % m) % m;
                    par[i][j][p] = (par[i][j][p - 1] + 1LL * basep[p - 1] * par[nx][ny][p - 1] % mod) % mod;
                }
            }
        }
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                int hsh = 0;
                int cur = k;
                int bas = 1;
                int nx = i, ny = j; 

                for(int l = L - 1; l >= 0; l--){
                    if((1<<l) <= cur){
                        hsh = (hsh + 1LL * bas * par[nx][ny][l] % mod) % mod;
                        nx = (nx + dx[s] * (1<<l) % n) % n,
                        ny = (ny + dy[s] * (1<<l) % m) % m;
                        bas = 1LL * bas * basep[l] % mod;
                        cur -= (1<<l);
                    }
                }
                mp[hsh]++;
            }
        }
    }

    ll toplam = 8LL * n * m;
    toplam = toplam * toplam;

    ll ist = 0;

    for(auto u: mp){
        ist += 1LL * u.ss * u.ss;
    }

    ll gc = __gcd(ist, toplam);

    ist /= gc;
    toplam /= gc;

    cout<<ist<<"/"<<toplam<<endl;

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
60.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 8 ms 748 KB Execution killed with signal 11
4 Runtime error 8 ms 1004 KB Execution killed with signal 11
5 Correct 7 ms 1004 KB Output is correct
6 Runtime error 13 ms 4352 KB Execution killed with signal 11
7 Runtime error 56 ms 18284 KB Execution killed with signal 11
8 Runtime error 179 ms 68716 KB Execution killed with signal 11