| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 921233 | coding_monk3 | Osmosmjerka (COCI17_osmosmjerka) | C++17 | 4100 ms | 137972 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("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// Miscellanous
#define ll long long
#define ull unsigned long long
#define si(x) scanf("%d",&x)
#define si2(x,y) scanf("%d %d",&x,&y)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define pi(x) printf("%d\n",x)
#define pi2(x,y) printf("%d %d\n",x,y)
#define pl(x) printf("%lld\n",x)
#define pl2(x,y) printf("%lld %lld\n",x,y)
#define ps(s) cout << s << endl
#define py printf("YES\n")
#define pn printf("NO\n")
#define pnl printf("\n")
#define pb push_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define clr(x) memset(x, 0, sizeof(x))
// Loops
#define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
#define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
#define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c))
#define rep(i,n) loop(i,0,n)
#define repn(i,n) loope(i,1,n)
// Constants
#define PI 3.1415926535897932384626
// Containers
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<string,string> pss;
typedef map<int, int> mii;
// Input Output
#define takei(a) int a; si(a)
#define takei2(a,b) int a,b; si2(a,b)
#define takel(a) ll a; sl(a)
#define takel2(a,b) ll a,b; sl2(a,b)
#define takearri0(n,a) vi a(n); rep(i,n) si(a[i])
#define takearri1(n,a) vi a(n+1); a[0] = 0; repn(i,n) si(a[i])
#define takearrl0(n,a) vl a(n); rep(i,n) sl(a[i])
#define takearrl1(n,a) vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i])
// Debug
void _print(int t) {cerr << t;}
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(unordered_set <T> v);
template <class T> void _print(unordered_multiset <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(unordered_map <T, V> v);
template <class T, class V> void _print(unordered_multimap <T, V> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x << " = "; _print(x); cerr << endl;
#else
#define deb(x)
#endif
inline string inttostr(ll a){
char x[100];
sprintf(x,"%lld",a); string s = x;
return s;
}
inline ll strtoint(string a){
char x[100]; ll res;
strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
return res;
}
inline string uppercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
return s;
}
inline string lowercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
return s;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
seed_seq seq{
(uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
(uint64_t) __builtin_ia32_rdtsc(),
(uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937_64 rng(seq);
const uint64_t MOD = (1ll << 61) - 1;
const ll BASE = uniform_int_distribution<ll>(2,MOD-1)(rng);
static inline ll add(ll x, ll y) {x+=y; return x >= MOD ? x-MOD : x;}
static inline ll sub(ll x, ll y) {x-=y; return x < 0 ? x+MOD : x;}
static inline uint64_t mul(uint64_t x,uint64_t y)
{
__int128_t z = (__int128_t)x*y;
z = (z&MOD) + (z>>61);
return z >= MOD ? z-MOD : z;
}
unordered_map<ll, int> mp;
int n,m,k;
// SPARSE TABLE
const int MAXN = 500;
const int LOGK = 30;
ll hash_[MAXN][MAXN][LOGK];
pii nxt[MAXN][MAXN][LOGK];
ll bpow[LOGK]; // bpow[i] = BASE ^ (2^i)
char v[MAXN][MAXN];
static inline int ADD(int i, int dx , int n)
{
i += dx;
if(i < 0) i += n;
else if(i >= n) i -= n;
return i;
}
static inline ll concat(ll l, ll r, ll factor) {return add(l, mul(r, factor));}
void init()
{
bpow[0] = BASE;
repn(x,LOGK-1) bpow[x] = mul(bpow[x-1] , bpow[x-1]);
}
void solve(int dx, int dy)
{
// BASE CASE
rep(i,n) rep(j,m) hash_[i][j][0] = v[i][j];
rep(i,n) rep(j,m) nxt[i][j][0] = {ADD(i,dx,n) , ADD(j,dy,m)};
// BUILDING TABLE
repn(k,LOGK-1)
{
rep(i,n) rep(j,m)
{
pii &pr = nxt[i][j][k-1];
nxt[i][j][k] = nxt[pr.ff][pr.ss][k-1];
hash_[i][j][k] = concat(hash_[i][j][k-1] , hash_[pr.ff][pr.ss][k-1] , bpow[k-1]);
}
}
rep(i,n) rep(j,m)
{
ll hash = 0, factor = 1;
int tmp_k = k, pi = i, pj = j;
for (int x = LOGK - 1; x >= 0; x--)
{
if((1<<x) <= tmp_k)
{
hash = concat(hash , hash_[pi][pj][x] , factor);
tmp_k -= (1<<x);
factor = mul(factor , bpow[x]);
pii &pr = nxt[pi][pj][x];
pi = pr.ff , pj = pr.ss;
}
}
mp[hash]++;
}
}
int main()
{
init();
scanf("%d%d%d", &n, &m, &k);
rep(i,n)
{
string s; cin >> s;
rep(j,m) v[i][j] = s[j];
}
loope(i,-1,1) loope(j,-1,1)
{
if(!i and !j) continue;
solve(i,j);
}
ll deno = 1ll * n*n*m*m*8*8;
ll num = 0;
for(auto &pr : mp) num += 1ll * pr.ss * pr.ss;
ll g = __gcd(num , deno);
num /= g, deno /= g;
printf("%lld/%lld\n", num, deno);
return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||