Submission #533836

#	Time	Username	Problem	Language	Result	Execution time	Memory
533836		Drew_	Sateliti (COCI20_satellti)	C++17	110 / 110	771 ms	5572 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ii pair<int, int>
#define f1 first
#define s2 second
#define mp make_pair

const int MAX = 1069;

int n, m;
int id[MAX];
bool grid[MAX][MAX];

void rotate()
{
	bool tmp[MAX][MAX];
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			tmp[i][j] = grid[n-i-1][m-j-1];

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			grid[i][j] = tmp[i][j];
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			char c; cin >> c;
			grid[i][j] = c == '.';
		}
	}

	rotate();

	for (int i = 0; i < n; ++i)
	{
		{
			bool allsame = true;
			for (int j = 1; j < m; ++j)
				if (grid[i][j] != grid[i][j-1])
					allsame = false;

			if (allsame)
			{
				id[i] = -1;
				continue;
			}
		}

		vector<int> ranks(m);
		for (int j = 0; j < m; ++j)
			ranks[j] = grid[i][j];	

		vector<array<int, 3>> v(m);
		for (int jump = 1; jump < m; jump <<= 1)
		{
			for (int j = 0; j < m; ++j)
				v[j] = {ranks[j], ranks[(j - jump + m) % m], j};
			sort(v.begin(), v.end());
	
			for (int j = 0, ctr = 0; j < m; ++j)
			{
				if (j) ctr += mp(v[j][0], v[j][1]) != mp(v[j-1][0], v[j-1][1]);
				ranks[v[j][2]] = ctr;
			}
		}

		id[i] = -1; //starting id, moves to the left
		for (int j = 0; j < m; ++j)
		{
			if (ranks[j] == 0)
			{
				if (id[i] == -1) id[i] = j;
				// else assert(0);
			}
		}
	}

	vector<int> vec(n);
	iota(vec.begin(), vec.end(), 0);

	sort(vec.begin(), vec.end(), [](const int &a, const int &b){
		if (id[a] == -1 && id[b] == -1)
			return grid[a][0] < grid[b][0];
		else if (id[a] == -1)
			return grid[a][0] == 0;
		else if (id[b] == -1)
			return grid[b][0] == 1;
		
		for (int i = 0; i < m; ++i)
		{
			bool lhs = grid[a][(id[a] - i + m) % m], rhs = grid[b][(id[b] - i + m) % m];
			if (lhs < rhs)	
				return true;
			else if (lhs > rhs)	
				return false;	
		}
		return false;
	});

	const auto same = [&](const int &a, const int &b)
	{
		if (id[a] == -1 && id[b] == -1)
			return grid[a][0] == grid[b][0];
		else if (id[a] != -1 && id[b] != -1)
		{
			for (int i = 0; i < m; ++i)
			{
				bool lhs = grid[a][(id[a] - i + m) % m], rhs = grid[b][(id[b] - i + m) % m];
				if (lhs != rhs)	
					return false;
			}
			return true;
		}
		return false;
	};

	vector<int> ranks(n);
	for (int i = 0, ctr = 0; i < n; ++i)
	{
		if (i && !same(vec[i], vec[i-1])) ctr++;
		ranks[vec[i]] = ctr;
	}

	vector<array<int, 3>> v(n);
	for (int jump = 1; jump < n; jump <<= 1)
	{
		for (int j = 0; j < n; ++j)
			v[j] = {ranks[j], ranks[(j - jump + n) % n], j};
		sort(v.begin(), v.end());

		for (int j = 0, ctr = 0; j < n; ++j)
		{
			if (j) ctr += mp(v[j][0], v[j][1]) != mp(v[j-1][0], v[j-1][1]);
			ranks[v[j][2]] = ctr;
		}
	}

	int start_id = -1;
	for (int i = 0; i < n; ++i)
	{
		if (ranks[i] == 0)
		{
			start_id = i;
			break;
		}
	}

	vector<string> ans;

	int shift = -1;
	for (int i = 0; i < n; ++i)
	{
		int j = (start_id - i + n) % n;
		if (shift == -1)
			shift = id[j];

		string s = "";
		if (shift == -1)
		{
			for (int k = 0; k < m; ++k)
				s += "*."[grid[j][k]]; 
		}
		else
		{
			for (int k = 0; k < m; ++k)
				s += "*."[grid[j][(shift - k + m) % m]];
			// reverse(s.begin(), s.end());
		}
		ans.pb(s);
	}

	for (int i = 0; i < n; ++i)
	{
		cout << ans[i] << '\n';
	}

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60