#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
using ii = pair<int, int>;
vector<pair<int, int>> dirs = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
int m, n;
struct Node{
int x, y;
char dir;
void add(int K){
x = (dirs[dir].first * K + x) % m;
y = (dirs[dir].second * K + y) % n;
if (x < 0) x += m;
if (y < 0) y += n;
}
Node operator + (int K){
Node res = *this; res.add(K); return res;
}
bool operator < (Node A) const {
return x < A.x;
}
};
int k;
vector<string> inp;
vector<pair<Node, int>> final;
int v[505][505][8];
void main_program(){
cin >> m >> n >> k;
inp.resize(m);
for (int i = 0; i < m; i++) cin >> inp[i];
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
for (char d = 0; d < 8; d++){
v[i][j][d] = inp[i][j] - 'a';
final.emplace_back(Node{i, j, d}, 0);
}
}
}
// for (int i = 0; i < m; i++){
// for (int j = 0; j < n; j++){
// for (int d = 0; d < 8; d++){
// cout << "v[" << i << "][" << j << "][" << d << "] = " << v[i][j][d] << "\n";
// }
// }
// }
int alr = 0;
for (int P = 1; P <= k; P <<= 1){
if (k & P){
vector<pair<Node, int>> newfinal;
vector<pair<ii, Node>> cmp;
for (auto [node, cls]: final){
Node n2 = node + alr;
cmp.emplace_back(pair{cls, v[n2.x][n2.y][n2.dir]}, node);
}
sort(cmp.begin(), cmp.end());
int CL = 0;
ii prev = {-1, -1};
for (auto [lst, node]: cmp){
if (lst != prev){
prev = lst; CL++;
}
newfinal.emplace_back(node, CL);
}
alr += P;
final.swap(newfinal);
}
vector<pair<ii, Node>> cmp;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
for (char d = 0; d < 8; d++){
Node nd{i, j, d};
Node nd2 = nd + P;
cmp.emplace_back(pair{v[i][j][d], v[nd2.x][nd2.y][d]}, nd);
}
}
}
sort(cmp.begin(), cmp.end());
int CL = 0;
ii lst = {-1, -1};
for (auto [pr, node]: cmp){
if (pr != lst){
lst = pr; CL++;
}
v[node.x][node.y][node.dir] = CL;
}
// for (int i = 0; i < m; i++){
// for (int j = 0; j < n; j++){
// for (int d = 0; d < 8; d++){
// cout << "v[" << i << "][" << j << "][" << d << "] = " << v[i][j][d] << "\n";
// }
// }
// }
}
#define int long long
map<int, int> result;
for (auto [node, cls]: final) result[cls]++;
int win = 0;
for (auto [key, value]: result) win += value * value;
int av = m * n * 8; av = av * av;
int g = __gcd(win, av);
win /= g; av /= g;
cout << win << "/" << av << "\n";
}
Compilation message
osmosmjerka.cpp: In function 'void main_program()':
osmosmjerka.cpp:51:13: warning: array subscript has type 'char' [-Wchar-subscripts]
51 | v[i][j][d] = inp[i][j] - 'a';
| ^
osmosmjerka.cpp:72:49: warning: array subscript has type 'char' [-Wchar-subscripts]
72 | cmp.emplace_back(pair{cls, v[n2.x][n2.y][n2.dir]}, node);
| ~~~^~~
osmosmjerka.cpp:93:36: warning: array subscript has type 'char' [-Wchar-subscripts]
93 | cmp.emplace_back(pair{v[i][j][d], v[nd2.x][nd2.y][d]}, nd);
| ^
osmosmjerka.cpp:93:56: warning: array subscript has type 'char' [-Wchar-subscripts]
93 | cmp.emplace_back(pair{v[i][j][d], v[nd2.x][nd2.y][d]}, nd);
| ^
osmosmjerka.cpp:105:27: warning: array subscript has type 'char' [-Wchar-subscripts]
105 | v[node.x][node.y][node.dir] = CL;
| ~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
5 ms |
684 KB |
Output is correct |
| 5 |
Correct |
29 ms |
1612 KB |
Output is correct |
| 6 |
Correct |
207 ms |
5592 KB |
Output is correct |
| 7 |
Correct |
2212 ms |
39384 KB |
Output is correct |
| 8 |
Execution timed out |
4045 ms |
143388 KB |
Time limit exceeded |
