Submission #834032

# Submission time Handle Problem Language Result Execution time Memory
834032 2023-08-22T10:16:16 Z vjudge1 Osmosmjerka (COCI17_osmosmjerka) C++17
100 / 160
4000 ms 131732 KB
#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

osmosmjerka.cpp:22:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   22 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
osmosmjerka.cpp:29:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   29 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
osmosmjerka.cpp:31:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   31 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
osmosmjerka.cpp:45:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   45 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
osmosmjerka.cpp:64:26: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   64 |     auto&operator[](Key x){
      |                          ^
osmosmjerka.cpp:64:26: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:64:26: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:64:26: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:72:16: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   72 |     auto begin(){return aps.begin();}
      |                ^
osmosmjerka.cpp:72:16: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:72:16: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:72:16: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:73:14: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   73 |     auto end(){return aps.end();}
      |              ^
osmosmjerka.cpp:73:14: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:73:14: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:73:14: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:75:22: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   75 | ull qpow(ull a,lint b){
      |                      ^
osmosmjerka.cpp:75:22: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:75:22: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:75:22: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:85:18: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   85 | void initpw(int x){
      |                  ^
osmosmjerka.cpp:85:18: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:85:18: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:85:18: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:90:39: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   90 |     lint a,lint b,lint n,lint m,lint k){
      |                                       ^
osmosmjerka.cpp:90:39: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:90:39: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:90:39: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp: In function 'auto solve(std::vector<std::__cxx11::basic_string<char> >&, lint, lint, lint, lint, lint)':
osmosmjerka.cpp:95:9: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   95 |     [&](){
      |         ^
osmosmjerka.cpp:95:9: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:95:9: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:95:9: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp: At global scope:
osmosmjerka.cpp:126:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  126 | int main(){
      |          ^
osmosmjerka.cpp:126:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:126:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:126:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 23764 KB Output isn't correct
2 Incorrect 15 ms 23764 KB Output isn't correct
3 Correct 14 ms 23812 KB Output is correct
4 Correct 16 ms 23936 KB Output is correct
5 Correct 23 ms 24220 KB Output is correct
6 Correct 81 ms 29048 KB Output is correct
7 Correct 863 ms 63124 KB Output is correct
8 Execution timed out 4078 ms 131732 KB Time limit exceeded