| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 834032 | vjudge1 | Osmosmjerka (COCI17_osmosmjerka) | C++17 | 4078 ms | 131732 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize(3)
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
using ull=unsigned long long;
using VU=vector<ull>;
const ull hashc=251;
template<typename Key,
typename T,class func=hash<Key>>
class cc_hash_table{
private:
static const int mem=1e6+7;
array<list<pair<Key,T>>,mem> ht;
func f;
list<T> aps;
public:
auto&operator[](Key x){
const int p=f(x)%mem;
for(auto&[k,t]:ht[p]) if(k==x)
return t;
aps.push_back(x);
ht[p].push_back({x,0});
return ht[p].back().second;
}
auto begin(){return aps.begin();}
auto end(){return aps.end();}
};
ull qpow(ull a,lint b){
ull res=1;
while(b){
if(b&1) res*=a;
a*=a;b>>=1;
}
return res;
}
cc_hash_table<ull,ull> cnx;
VU pw;
void initpw(int x){
pw.clear();pw.resize(x);
cir(i,0,x) pw[i]=qpow(hashc,i);
}
auto solve(vector<string>&s,
lint a,lint b,lint n,lint m,lint k){
const int __lg2=log2(k)+2;
initpw(__lg2);
vector<vector<VU>> g(
n,vector<VU>(m,VU(__lg2)));
[&](){
cir(i,0,n) cir(j,0,m)
g[i][j][0]=s[i][j];
}();
cir(x,1,__lg2){
cir(i,0,n) cir(j,0,m){
const int ni=((i+a*(
((1<<x)>>1)))%n+n)%n;
const int nj=((j+b*(
((1<<x)>>1)))%m+m)%m;
g[i][j][x]=g[i][j][x-1]*
(x?pw[x-1]:(ull)(0))
+g[ni][nj][x-1];
}
}
cir(i,0,n) cir(j,0,m){
ull alw=0;
int ix=i,jx=j,w=k;
cir(x,0,__lg2){
if(k&(1<<x)){
alw+=g[ix][jx][x]*
qpow(hashc,w-=(1<<x));
ix=((ix+a*((
(1<<x)>>1)+1))%n+n)%n;
jx=((jx+b*((
(1<<x)>>1)+1))%m+m)%m;
}
}
++cnx[alw];
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n,m,k;cin>>n>>m>>k;
vector<string> s(n);
for(auto&i:s) cin>>i;
cir(a,-1,2) cir(b,-1,2) if(a||b){
solve(s,a,b,n,m,k);
}
lint ans=0;
for(auto&x:cnx)
ans+=qpow(cnx[x],2);
const lint all=qpow(n*m*8,2);
const lint g=__gcd(ans,all);
cout<<ans/g<<'/'<<all/g<<'\n';
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||