oj.uz

Submission #477707

# Submission time Handle Problem Language Result Execution time Memory
477707 2021-10-03T07:52:42 Z MohammadAghil Osmosmjerka (COCI17_osmosmjerka) C++14
140 / 160
 4000 ms 73956 KB 
#include <bits/stdc++.h> 
  using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 

// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll maxn = 5e2 + 5, inf = 1e9 + 5, p = 9973, lg = 31;

ll mod[2] = {ll(1e9 + 9), ll(1e9 + 7)};
ll jmp[maxn][maxn][lg];
int n, m, k; 
ll pw[lg][2];
pp st[maxn*maxn*10];

ll add(ll a, ll b, ll c, ll md){
    return (a + ((1LL << b)%md)*c + md)%md;
}

void calc(int x, int y, int id, int c){
    rep(k,1,lg){
        rep(i,0,n){
            rep(j,0,m){
                jmp[i][j][k] = (jmp[i][j][k-1]*pw[k-1][id]%mod[id] + 
                    jmp[add(i, k-1, x,  n)][add(j, k-1, y,  m)][k-1])%mod[id];
            }
        }
    }
    rep(i,0,n){
        rep(j,0,m){
            ll res = 0;
            pp cr = {i, j};
            rep(b,0,lg){
                if(k&(1LL << b)){
                    res = (res*pw[b][id]%mod[id] + jmp[cr.ff][cr.ss][b])%mod[id];
                    cr.ff = add(cr.ff, b, x, n);
                    cr.ss = add(cr.ss, b, y, m);
                }
            }
            if(id) st[c++].ff = res;
            else st[c++].ss = res;
        }
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> k;
    rep(i,0,n){
        rep(j,0,m){
            char c; cin >> c;
            jmp[i][j][0] = int(c);
        }
    }    
    pw[0][0] = pw[0][1] = p;
    rep(i,1,lg){
        pw[i][0] = 1LL*pw[i-1][0]*pw[i-1][0]%mod[0];
        pw[i][1] = 1LL*pw[i-1][1]*pw[i-1][1]%mod[1];
    }
    int cr = 0;
    rep(i,-1,2){
        rep(j,-1,2){
            if(i == 0 && j == 0) continue;
            calc(i, j, 0, cr); calc(i, j, 1, cr);
            cr += n*m;
        }
    }
    sort(st, st + cr);
    pp lst = {-1, -1};
    ll cnt = 0;
    ll t = 0, b = 64LL*n*n*m*m;
    rep(i,0,cr){
        if(lst != st[i]){
            t += 1LL*cnt*cnt;
            cnt = 0;
        }
        lst = st[i];
        cnt++;
    } t += cnt*cnt;
    ll g = __gcd(t, b);
    cout << t/g << '/' << b/g;
    return 0;
}

Subtask #1
140.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 460 KB Output is correct
5 Correct 25 ms 844 KB Output is correct
6 Correct 136 ms 3140 KB Output is correct
7 Correct 1391 ms 19448 KB Output is correct
8 Execution timed out 4078 ms 73956 KB Time limit exceeded