oj.uz

Submission #604514

# Submission time Handle Problem Language Result Execution time Memory
604514 2022-07-25T07:13:41 Z tutis L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 53 ms 712 KB 
/*input
4 3 3
1 1
1 3
4 3
*/

#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T,  null_type,  less<T>,  rb_tree_tag,  tree_order_statistics_node_update>;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int W, H, K;
	cin >> W >> H >> K;
	map<int, int>A;
	while (K--)
	{
		int x, y;
		cin >> x >> y;
		if (A.count(y) == 0)
			A[y] = 0;
		A[y] |= 1 << (x - 1);
	}
	bitset < 1 << 13 > gal;
	gal[(1 << W) - 1] = true;
	vector<int>X[1 << 13];
	A[H + 1] = 0;
	for (int i = 1; i <= H;)
	{
		int msk = 0;
		function<void(int, int, int)>dfs = [&](int i, int m1, int m2)
		{
			if (i == W - 1)
			{
				if (m1 == (1 << W) - 1)
					X[msk].push_back(m2);
				return;
			}
			for (int da : {0, 1})
			{
				for (int db : {0, 1})
				{
					int m[2] = {m1, m2};
					bool ok = true;
					for (int dx : {0, 1})
					{
						for (int dy : {0, 1})
						{
							if (dx == da && dy == db)
								continue;
							if ((m[dx] & (1 << (i + dy))) != 0)
								ok = false;
							m[dx] |= 1 << (i + dy);
						}
					}
					if (ok)
						dfs(i + 1, m[0], m[1]);
				}
			}
			dfs(i + 1, m1, m2);
		};
		if (A[i] == 0)
		{
			int i1 = A.upper_bound(i)->first;
			vector < bitset < 1 << 13>>V = {gal};
			for (int t = 1; t <= (i1 - i); t++)
			{
				bitset < 1 << 13 > gal_;
				for (msk = 0; msk < (1 << W); msk++)
					if (gal[msk])
					{
						if (X[msk].empty())
							dfs(0, msk, 0);
						for (int msk1 : X[msk])
							if ((msk1 & A[i]) == 0)
								gal_[msk1 | A[i]] = true;
					}
				gal = gal_;
				V.push_back(gal);
				for (int k = t - 1; k >= 0; k--)
					if (V[k] == V[t])
					{
						gal = V[k + ((i1 - i) % (t - k))];
						t = i1 - i + 1;
						break;
					}
			}
			i = i1;
		}
		else {
			bitset < 1 << 13 > gal_;
			for (msk = 0; msk < (1 << W); msk++)
				if (gal[msk])
				{
					if (X[msk].empty())
						dfs(0, msk, 0);
					for (int msk1 : X[msk])
						if ((msk1 & A[i]) == 0)
							gal_[msk1 | A[i]] = true;
				}
			gal = gal_;
			i++;
		}
	}
	if (gal[(1 << W) - 1])
		cout << "YES\n";
	else
		cout << "NO\n";
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 53 ms 620 KB Output is correct
6 Correct 49 ms 712 KB Output is correct
7 Incorrect 12 ms 596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Incorrect 4 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -