Submission #696358

#	Time	Username	Problem	Language	Result	Execution time	Memory
696358		TranGiaHuy1508	Osmosmjerka (COCI17_osmosmjerka)	C++17	140 / 160	4045 ms	143388 KiB

osmosmjerka

#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 (stderr)

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;
      |                      ~~~~~^~~

• Subtask 1: 140 / 160