Submission #119913

#	Time	Username	Problem	Language	Result	Execution time	Memory
119913		tutis	Trapezi (COI17_trapezi)	C++17	63 / 100	1068 ms	33356 KiB

trapezi

/*input
5
00000000000
0000000000000
0000000.0000000
000..0000.0000000
00.0.00000.00000.0.
00.000000000000.000
00000000000000000
0000000.000...0
0000000000000
00000000000
*/
#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;
};
struct BitSet
{
	unsigned long long x, y, z;
	BitSet operator~()
	{
		BitSet ret;
		ret.x = ~x;
		ret.y = ~y;
		ret.z = ~z;
		return ret;
	}
	bool operator<(const BitSet &o)const
	{
		if (x != o.x)
			return x < o.x;
		if (y != o.y)
			return y < o.y;
		return z < o.z;
	}
	BitSet operator&(const BitSet &other)
	{
		BitSet ret;
		ret.x = x & other.x;
		ret.y = y & other.y;
		ret.z = z & other.z;
		return ret;
	}
	void set(int i)
	{
		if (i < 64)
		{
			x |= (1ull << i);
		}
		else if (i < 128)
		{
			y |= (1ull << (i - 64));
		}
		else
		{
			z |= (1ull << (i - 128));
		}
	}
	void unset(int i)
	{
		if (i < 64)
		{
			x &= ~(1ull << i);
		}
		else if (i < 128)
		{
			y &= ~(1ull << (i - 64));
		}
		else
		{
			z &= ~(1ull << (i - 128));
		}
	}
	bool get(int i)
	{
		if (i < 64)
		{
			return (x & (1ull << (i))) != 0;
		}
		else if (i < 128)
		{
			return (y & (1ull << (i - 64))) != 0;
		}
		else
		{
			return (z & (1ull << (i - 128))) != 0;
		}
	}
};
vector<grupe>xx;
vector<char>col;
BitSet x;
BitSet prad;
int timer = 0;
vector<int>jj[150];
bitset<390>xxxxx;
map<BitSet, bitset<390>>M;
set<BitSet>buvau[150];
int n;
int riba;
void ieskom(int i)
{
	if (i > riba || buvau[i].count(x))
		return;
	buvau[i].insert(x);
	M[x] = xxxxx;
	if (x.get(i) == false)
		return ieskom(i + 1);
	for (int j : jj[i])
	{
		if (x.get(xx[j].x) && x.get(xx[j].y) && x.get(xx[j].z))
		{
			x.unset(xx[j].x);
			x.unset(xx[j].y);
			x.unset(xx[j].z);
			xxxxx[j] = true;
			ieskom(i + 1);
			xxxxx[j] = false;
			x.set(xx[j].x);
			x.set(xx[j].y);
			x.set(xx[j].z);
		}
	}
}
bool ieskom1(int i)
{
	M[x] = xxxxx;
	BitSet y = (~x)&prad;
	if (M.count(y))
	{
		auto xxx = M[y];
		for (int i = 0; i < (int)xx.size(); i++)
			if (xxx[i])
				xx[i].reikia = true;
		return true;
	}
	if (i < riba)
		return false;
	if (x.get(i) == false)
		return ieskom1(i - 1);
	for (int j : jj[i])
	{
		if (x.get(xx[j].x) && x.get(xx[j].y) && x.get(xx[j].z))
		{
			x.unset(xx[j].x);
			x.unset(xx[j].y);
			x.unset(xx[j].z);
			xx[j].reikia = true;
			if (ieskom1(i - 1))
				return true;
			xx[j].reikia = false;
			x.set(xx[j].x);
			x.set(xx[j].y);
			x.set(xx[j].z);
		}
	}
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n;
	string s[2 * n];
	for (int i = 0; i < 2 * n; i++)
		cin >> s[i];
	int kiek = 0;
	vector<int>id[2 * n];
	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++;
		}
	riba = timer / 3;
	vector<int>adj[timer];
	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 = 0; 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;
					xx.push_back(a);
				}
			}
		}
	}
	for (int i = 0; i < (int)xx.size(); i++)
	{
		jj[xx[i].x].push_back(i);
		jj[xx[i].y].push_back(i);
		jj[xx[i].z].push_back(i);
	}
	for (int i = 0; i < 2 * n; i++)
	{
		for (int t = 0; t < (int)id[i].size(); t++)
		{
			if (s[i][t] == '0')
				x.set(id[i][t]);
		}
	}
	prad = x;
	ieskom(0);
	if (ieskom1(timer - 1))
	{
		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 << '\n';
		}
	}
	else
		cout << "nemoguce\n";
}

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