Submission #477706

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477706	2021-10-03T07:47:00 Z	MohammadAghil	Osmosmjerka (COCI17_osmosmjerka)	C++14	140 / 160	4000 ms	81072 KB

osmosmjerka

#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];
vector<pp> st;

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

vector<int> calc(int x, int y, int id){
    vector<int> ans;
    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);
                }
            }
            ans.pb(res);
        }
    }
    return ans;
}

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];
    }
    rep(i,-1,2){
        rep(j,-1,2){
            if(i == 0 && j == 0) continue;
            vector<int> a1 = calc(i, j, 0), a2 = calc(i, j, 1);
            rep(i,0,sz(a1)){
                st.pb({a1[i], a2[i]});
            }
        }
    }
    sort(all(st));
    pp lst = {-1, -1};
    ll cnt = 0;
    ll t = 0, b = 64LL*n*n*m*m;
    rep(i,0,sz(st)){
        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	26 ms	1124 KB	Output is correct
6	Correct	135 ms	3284 KB	Output is correct
7	Correct	1408 ms	20628 KB	Output is correct
8	Execution timed out	4070 ms	81072 KB	Time limit exceeded