Submission #854533

#TimeUsernameProblemLanguageResultExecution timeMemory
854533smirichtoOsmosmjerka (COCI17_osmosmjerka)C++17
80 / 160
4085 ms10816 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back #define pi pair<ll,ll> #define F first #define S second #define all(x) (x).begin(), (x).end() #define alll(x) ((x).begin()+1), (x).end() #define clean(v) (v).resize(distance((v).begin(), unique(all(v)))); #define yes cout<<"Yes"<<endl; #define no cout<<"No"<<endl; #define mod mod #define endl '\n' mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 998244353; void io() { ios::sync_with_stdio(false); cin.tie(NULL); } template<class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<class T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } void nop() { cout << -1 << endl; return; } long long exp(long long x, long long y, long long p = mod) { long long res = 1; x %= p; while (y) { if (y & 1) { res *= x; res %= p; } x *= x; x %= p; y >>= 1; } return res; } const int N = 505 ; char tab[N][N] ; int di[] = {-1 , -1 , -1 , 0 , 1 , 1 , 1 , 0}; int dj[] = {-1 , 0 , 1 ,1 , 1 ,0 , -1 , -1}; int n , m , kk; int base = 9973 ; int get(char c){ return c - 'a' ; } ll get_hash(int si , int sj , int dir , int len = 0) { if(len==min(n , kk)) return 0 ; return get(tab[si][sj]) + (base * get_hash((si + di[dir] + n) % n , (sj + dj[dir] + n)%n , dir , len+1) % mod) % mod ; } void solve() { cin>>n>>m>>kk ; for(int i = 0 ; i<n ; i++){ for(int j = 0 ; j<m ; j++){ cin>>tab[i][j] ; } } if(n!=m) assert(false) ; ll good = 0 ; vector<ll> v ; for(int i = 0 ; i<n ; i++){ for(int j = 0 ; j<m ; j++){ for(int k = 0 ; k<8 ; k++){ v.pb(get_hash(i , j , k)) ; } } } sort(all(v)) ; for(int i = 0 ; i<v.size() ; i++){ int j = i ; while(j+1<v.size() && v[j+1]==v[i]) ++j ; ll len = j - i + 1 ; good += len * len ; i = j ; } ll tot = n * m * 8 ;tot *= tot ; ll gd = __gcd(tot , good) ; if(n!=m) assert(false) ; cout<<good / gd<<"/"<<tot/gd<<endl; } int main() { io(); ll tt = 1; //cin>>tt ; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

osmosmjerka.cpp: In function 'void solve()':
osmosmjerka.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i = 0 ; i<v.size() ; i++){
      |                     ~^~~~~~~~~
osmosmjerka.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         while(j+1<v.size() && v[j+1]==v[i]) ++j ;
      |               ~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...