oj.uz

Submission #533836

# Submission time Handle Problem Language Result Execution time Memory
533836 2022-03-07T11:48:12 Z Drew_ Sateliti (COCI20_satellti) C++17
110 / 110
 771 ms 5572 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 1 ms 1468 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 1 ms 1468 KB Output is correct
8 Correct 52 ms 1988 KB Output is correct
9 Correct 3 ms 1356 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 5 ms 1996 KB Output is correct
12 Correct 5 ms 2000 KB Output is correct
13 Correct 7 ms 1996 KB Output is correct
14 Correct 11 ms 1996 KB Output is correct
15 Correct 31 ms 1972 KB Output is correct
16 Correct 35 ms 1988 KB Output is correct
17 Correct 4 ms 1996 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 1 ms 1468 KB Output is correct
8 Correct 52 ms 1988 KB Output is correct
9 Correct 3 ms 1356 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 5 ms 1996 KB Output is correct
12 Correct 5 ms 2000 KB Output is correct
13 Correct 7 ms 1996 KB Output is correct
14 Correct 11 ms 1996 KB Output is correct
15 Correct 31 ms 1972 KB Output is correct
16 Correct 35 ms 1988 KB Output is correct
17 Correct 4 ms 1996 KB Output is correct
18 Correct 771 ms 5376 KB Output is correct
19 Correct 4 ms 2500 KB Output is correct
20 Correct 15 ms 1488 KB Output is correct
21 Correct 31 ms 5504 KB Output is correct
22 Correct 29 ms 5396 KB Output is correct
23 Correct 83 ms 5508 KB Output is correct
24 Correct 107 ms 5572 KB Output is correct
25 Correct 432 ms 5504 KB Output is correct
26 Correct 513 ms 5444 KB Output is correct
27 Correct 29 ms 5444 KB Output is correct