Submission #1220698

#TimeUsernameProblemLanguageResultExecution timeMemory
1220698super0200Osmosmjerka (COCI17_osmosmjerka)C++20
100 / 160
510 ms35480 KiB
#define _GLIBCXX_FILESYSTEM #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define F first #define S second #define int long long using namespace std; int n,m,k; int b=31; int mod=(1ll<<61)-1; map<int,int> mp; void roh(string x) { int sz=min((int)x.size(),k); vector<__int128> h(x.size()); vector<__int128> p(x.size()); p[0]=1; h[0]=x[0]; for(int i=1; i<x.size(); i++) { p[i]=(p[i-1]*b)%mod; h[i]=((h[i-1]*b)%mod+x[i] )%mod; } int l1,l2,r1,r2; for(int i=0; i<x.size(); i++) { l1=l2=r1=r2=-1; l1=i; r1 =min((int)x.size()-1,i+sz-1); if(r1-l1+1 <sz) { l2=0; int need=sz-(r1-l1+1); r2=need-1; } int value=0; if(l2==-1) { if(l1==0) value=h[r1]; else value=((h[r1]-(h[l1-1]*p[r1-l1+1]%mod))+mod)%mod; } else { __int128 value1=h[r2]; __int128 value2=(h[r1]-((h[l1-1]*p[r1-l1+1])%mod)+mod)%mod; value=(value1+ (value2*p[r2+1])%mod)%mod; } mp[(int)value]++; } } signed main() { IOS mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); b=uniform_int_distribution<int>(0,1e9)(rnd); cin>>n>>m>>k; vector<vector<char>> grid(n,vector<char>(m)); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>grid[i][j]; } } for(int i=0; i<n; i++) { string x; for(int j=0; j<m; j++) { x.push_back(grid[i][j]); } roh(x); reverse(x.begin(),x.end()); roh(x); } for(int j=0; j<m; j++) { string x; for(int i=0; i<n; i++) { x.push_back(grid[i][j]); } roh(x); reverse(x.begin(),x.end()); roh(x); } vector<vector<int>> vis(n,vector<int>(m)); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(!vis[i][j]) { string x; vis[i][j]=true; x.push_back(grid[i][j]); int ii=(i-1+n)%n; int jj=(j-1+m)%m; while(ii!=i || jj!=j) { vis[ii][jj]=true; x.push_back(grid[ii][jj]); ii=(ii-1+n)%n; jj=(jj-1+m)%m; } roh(x); // reverse(x.begin(),x.end()); // roh(x); } } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { vis[i][j]=0; } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(!vis[i][j]) { string x; vis[i][j]=true; x.push_back(grid[i][j]); int ii=(i+1+n)%n; int jj=(j+1+m)%m; while(ii!=i || jj!=j) { vis[ii][jj]=true; x.push_back(grid[ii][jj]); ii=(ii+1)%n; jj=(jj+1)%m; } roh(x); // reverse(x.begin(),x.end()); // roh(x); } } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { vis[i][j]=0; } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(!vis[i][j]) { string x; vis[i][j]=true; x.push_back(grid[i][j]); int ii=(i-1+n)%n; int jj=(j+1+m)%m; while(ii!=i || jj!=j) { vis[ii][jj]=true; x.push_back(grid[ii][jj]); ii=(ii-1+n)%n; jj=(jj+1)%m; } roh(x); //reverse(x.begin(),x.end()); //roh(x); } } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { vis[i][j]=0; } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(!vis[i][j]) { string x; vis[i][j]=true; x.push_back(grid[i][j]); int ii=(i+1)%n; int jj=(j-1+m)%m; while(ii!=i || jj!=j) { vis[ii][jj]=true; x.push_back(grid[ii][jj]); ii=(ii+1)%n; jj=(jj-1+m)%m; } roh(x); //reverse(x.begin(),x.end()); //roh(x); } } } int num,den; num=0; den=n*m*8*n*m*8; for(auto [a,b]:mp) { num+= (b*b); } int g=gcd(num,den); cout<<(num/g)<<"/"<<(den/g); }
#Verdict Execution timeMemoryGrader output
Fetching results...