Submission #119819

#	Time	Username	Problem	Language	Result	Execution time	Memory
119819		tutis	Trapezi (COI17_trapezi)	C++17	23 / 100	1074 ms	512 KiB

trapezi

/*input
2
0000.
0000000
..00.0.
.0000
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct grupe
{
	int x, y, z;
	bool reikia = false;
};
vector<grupe>xx;
vector<char>col = {'.'};
int kiek = 0;
vector<int>adj[1000];
bool ieskom(int i)
{
	if (kiek == 0)
		return true;
	if (i == (int)xx.size())
	{
		return false;
	}
	if (col[xx[i].x] != '0' || col[xx[i].y] != '0' || col[xx[i].z] != '0')
	{
		return ieskom(i + 1);
	}
	col[xx[i].x] = '1';
	col[xx[i].y] = '1';
	col[xx[i].z] = '1';
	xx[i].reikia = true;
	kiek -= 3;
	{
		set<int>aplink;
		for (int i : {xx[i].x, xx[i].y, xx[i].z})
			for (int j : adj[i])
				aplink.insert(j);
		bool ok = true;
		for (int x : aplink)
		{
			if (col[x] == '0')
			{
				int kiek = 0;
				int yy = x;
				for (int y : adj[x])
				{
					if (col[y] == '0')
					{
						yy = y;
						kiek++;
					}
				}
				if (kiek == 0)
					ok = false;
				else if (kiek == 1)
				{
					for (int y : adj[yy])
					{
						if (col[y] == '0')
						{
							kiek++;
						}
					}
					if (kiek == 2)
						ok = false;
				}
			}
		}
		if (ok && ieskom(i + 1))
			return true;
	}
	xx[i].reikia = false;
	kiek += 3;
	col[xx[i].x] = '0';
	col[xx[i].y] = '0';
	col[xx[i].z] = '0';
	return ieskom(i + 1);
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	string s[2 * n];
	for (int i = 0; i < 2 * n; i++)
		cin >> s[i];
	vector<int>id[2 * n];
	int timer = 1;
	for (int i = 0; i < 2 * n; i++)
		for (char c : s[i])
		{
			id[i].push_back(timer++);
			col.push_back(c);
			if (c == '0')
				kiek++;
		}
	for (int i = 0; i < 2 * n; i++)
	{
		for (int t = 0; t + 1 < (int)id[i].size(); t++)
		{
			int x = id[i][t];
			int y = id[i][t + 1];
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
	}
	for (int i = 0; i <= n - 2; i++)
	{
		for (int t = 0; t < (int)id[i].size(); t += 2)
		{
			int x = id[i][t];
			int y = id[i + 1][t + 1];
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
	}
	for (int t = 0; t < (int)id[n - 1].size(); t += 2)
	{
		int x = id[n - 1][t];
		int y = id[n][t];
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for (int i = n + 1; i < 2 * n; i++)
	{
		for (int t = 0; t < (int)id[i].size(); t += 2)
		{
			int x = id[i][t];
			int y = id[i - 1][t + 1];
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
	}
	for (int i = 1; i < timer; i++)
	{
		for (int j : adj[i])
		{
			for (int k : adj[i])
			{
				if (j < k)
				{
					grupe a;
					a.x = i;
					a.y = j;
					a.z = k;
					if (col[a.x] == '0' && col[a.y] == '0' && col[a.z] == '0')
						xx.push_back(a);
				}
			}
		}
	}
	if (ieskom(0))
	{
		for (grupe a : xx)
		{
			if (a.reikia == false)
				continue;
			set<int>aplink;
			for (int i : {a.x, a.y, a.z})
				for (int j : adj[i])
					aplink.insert(j);
			for (int i : {a.x, a.y, a.z})
				aplink.erase(i);
			set<char>cols;
			for (int i : aplink)
				cols.insert(col[i]);
			for (char x = '1'; x <= '6'; x++)
				if (cols.count(x) == 0)
				{
					col[a.x] = x;
					col[a.y] = x;
					col[a.z] = x;
				}
		}
		for (int i = 0; i < 2 * n; i++)
		{
			for (int t = 0; t < (int)id[i].size(); t++)
			{
				cout << col[id[i][t]];
			}
			cout << endl;
		}
	}
	else
		cout << "nemoguce\n";
}

• Subtask 1: 6 / 6
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 22
• Subtask 5: 0 / 37