Submission #921229

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
921229	2024-02-03T14:57:48 Z	coding_monk3	Osmosmjerka (COCI17_osmosmjerka)	C++17	140 / 160	4000 ms	144496 KB

osmosmjerka

#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;
}

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()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  init();

  cin >> 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;

  cout << num << '/' << deno << '\n';
  return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Compilation message

osmosmjerka.cpp: In function 'std::string uppercase(std::string)':
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:117:3: note: in expansion of macro 'rep'
  117 |   rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
      |   ^~~
osmosmjerka.cpp: In function 'std::string lowercase(std::string)':
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:123:3: note: in expansion of macro 'rep'
  123 |   rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
      |   ^~~
osmosmjerka.cpp: In function 'long long int add(long long int, long long int)':
osmosmjerka.cpp:139:50: warning: comparison of integer expressions of different signedness: 'long long int' and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
  139 | static inline ll add(ll x, ll y) {x+=y; return x >= MOD ? x-MOD : x;}
      |                                                ~~^~~~~~
osmosmjerka.cpp: In function 'void init()':
osmosmjerka.cpp:32:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   32 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
osmosmjerka.cpp:35:19: note: in expansion of macro 'loope'
   35 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
osmosmjerka.cpp:173:3: note: in expansion of macro 'repn'
  173 |   repn(x,LOGK-1) bpow[x] = mul(bpow[x-1] , bpow[x-1]);
      |   ^~~~
osmosmjerka.cpp: In function 'void solve(int, int)':
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:179:5: note: in expansion of macro 'rep'
  179 |     rep(i,n) rep(j,m) hash_[i][j][0] = v[i][j];
      |     ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:179:14: note: in expansion of macro 'rep'
  179 |     rep(i,n) rep(j,m) hash_[i][j][0] = v[i][j];
      |              ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:180:5: note: in expansion of macro 'rep'
  180 |     rep(i,n) rep(j,m) nxt[i][j][0] = {ADD(i,dx,n) , ADD(j,dy,m)};
      |     ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:180:14: note: in expansion of macro 'rep'
  180 |     rep(i,n) rep(j,m) nxt[i][j][0] = {ADD(i,dx,n) , ADD(j,dy,m)};
      |              ^~~
osmosmjerka.cpp:32:31: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   32 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
osmosmjerka.cpp:35:19: note: in expansion of macro 'loope'
   35 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
osmosmjerka.cpp:183:5: note: in expansion of macro 'repn'
  183 |     repn(k,LOGK-1)
      |     ^~~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:185:9: note: in expansion of macro 'rep'
  185 |         rep(i,n) rep(j,m)
      |         ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:185:18: note: in expansion of macro 'rep'
  185 |         rep(i,n) rep(j,m)
      |                  ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:194:5: note: in expansion of macro 'rep'
  194 |     rep(i,n) rep(j,m)
      |     ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:194:14: note: in expansion of macro 'rep'
  194 |     rep(i,n) rep(j,m)
      |              ^~~
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:222:3: note: in expansion of macro 'rep'
  222 |   rep(i,n)
      |   ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
   34 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:225:5: note: in expansion of macro 'rep'
  225 |     rep(j,m) v[i][j] = s[j];
      |     ^~~
osmosmjerka.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
osmosmjerka.cpp:228:3: note: in expansion of macro 'loope'
  228 |   loope(i,-1,1) loope(j,-1,1)
      |   ^~~~~
osmosmjerka.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   32 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
osmosmjerka.cpp:228:17: note: in expansion of macro 'loope'
  228 |   loope(i,-1,1) loope(j,-1,1)
      |                 ^~~~~

Subtask #1

140.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4444 KB	Output is correct
2	Correct	1 ms	4564 KB	Output is correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	3 ms	8792 KB	Output is correct
5	Correct	9 ms	12892 KB	Output is correct
6	Correct	55 ms	29728 KB	Output is correct
7	Correct	1317 ms	70968 KB	Output is correct
8	Execution timed out	4026 ms	144496 KB	Time limit exceeded