Submission #921218

#TimeUsernameProblemLanguageResultExecution timeMemory
921218coding_monk3Osmosmjerka (COCI17_osmosmjerka)C++17
140 / 160
4022 ms197264 KiB
#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]; pll 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 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)}; bpow[0] = BASE; // BUILDING TABLE repn(k,LOGK-1) { rep(i,n) rep(j,m) { pll &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]); } bpow[k] = mul(bpow[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]); pll &pr = nxt[pi][pj][x]; pi = pr.ff , pj = pr.ss; } } mp[hash]++; } } int main() { si2(n,m); si(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 (stderr)

osmosmjerka.cpp: In function 'std::string uppercase(std::string)':
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:115:3: note: in expansion of macro 'rep'
  115 |   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:29:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:121:3: note: in expansion of macro 'rep'
  121 |   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:137:50: warning: comparison of integer expressions of different signedness: 'long long int' and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
  137 | static inline ll add(ll x, ll y) {x+=y; return x >= MOD ? x-MOD : x;}
      |                                                ~~^~~~~~
osmosmjerka.cpp: In function 'void solve(int, int)':
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:171:5: note: in expansion of macro 'rep'
  171 |     rep(i,n) rep(j,m) hash_[i][j][0] = v[i][j];
      |     ^~~
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:171:14: note: in expansion of macro 'rep'
  171 |     rep(i,n) rep(j,m) hash_[i][j][0] = v[i][j];
      |              ^~~
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:172:5: note: in expansion of macro 'rep'
  172 |     rep(i,n) rep(j,m) nxt[i][j][0] = {ADD(i,dx,n) , ADD(j,dy,m)};
      |     ^~~
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:172:14: note: in expansion of macro 'rep'
  172 |     rep(i,n) rep(j,m) nxt[i][j][0] = {ADD(i,dx,n) , ADD(j,dy,m)};
      |              ^~~
osmosmjerka.cpp:30:31: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   30 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
osmosmjerka.cpp:33:19: note: in expansion of macro 'loope'
   33 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
osmosmjerka.cpp:176:5: note: in expansion of macro 'repn'
  176 |     repn(k,LOGK-1)
      |     ^~~~
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:178:9: note: in expansion of macro 'rep'
  178 |         rep(i,n) rep(j,m)
      |         ^~~
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:178:18: note: in expansion of macro 'rep'
  178 |         rep(i,n) rep(j,m)
      |                  ^~~
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:188:5: note: in expansion of macro 'rep'
  188 |     rep(i,n) rep(j,m)
      |     ^~~
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:188:14: note: in expansion of macro 'rep'
  188 |     rep(i,n) rep(j,m)
      |              ^~~
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:211:3: note: in expansion of macro 'rep'
  211 |   rep(i,n)
      |   ^~~
osmosmjerka.cpp:29:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
osmosmjerka.cpp:32:18: note: in expansion of macro 'loop'
   32 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
osmosmjerka.cpp:214:5: note: in expansion of macro 'rep'
  214 |     rep(j,m) v[i][j] = s[j];
      |     ^~~
osmosmjerka.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
osmosmjerka.cpp:217:3: note: in expansion of macro 'loope'
  217 |   loope(i,-1,1) loope(j,-1,1)
      |   ^~~~~
osmosmjerka.cpp:30:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   30 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
osmosmjerka.cpp:217:17: note: in expansion of macro 'loope'
  217 |   loope(i,-1,1) loope(j,-1,1)
      |                 ^~~~~
osmosmjerka.cpp:8:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
osmosmjerka.cpp:210:3: note: in expansion of macro 'si2'
  210 |   si2(n,m); si(k);
      |   ^~~
osmosmjerka.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
osmosmjerka.cpp:210:13: note: in expansion of macro 'si'
  210 |   si2(n,m); si(k);
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...