Submission #604509

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
604509	2022-07-25T07:12:11 Z	tutis	L-triominoes (CEOI21_ltriominoes)	C++17	10 / 100	2338 ms	524288 KB

ltrominoes

/*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 = 0; k < t; k++)
				// 	if (V[k] == V[t])
				// 	{
				// 		gal = V[k + ((i1 - i) % (t - k))];
				// 		t = i1 - i;
				// 	}
			}
			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

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1688 KB	Output is correct
2	Correct	2 ms	1160 KB	Output is correct
3	Correct	3 ms	1316 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	5 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	87 ms	900 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	5 ms	640 KB	Output is correct
11	Correct	128 ms	912 KB	Output is correct
12	Correct	13 ms	880 KB	Output is correct
13	Correct	1 ms	516 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	82 ms	620 KB	Output is correct
16	Correct	2338 ms	2164 KB	Output is correct
17	Correct	97 ms	712 KB	Output is correct
18	Correct	860 ms	1160 KB	Output is correct
19	Correct	6 ms	596 KB	Output is correct
20	Correct	2252 ms	2244 KB	Output is correct
21	Correct	759 ms	1160 KB	Output is correct
22	Correct	3 ms	1668 KB	Output is correct
23	Correct	7 ms	516 KB	Output is correct
24	Correct	3 ms	1112 KB	Output is correct
25	Correct	2089 ms	2248 KB	Output is correct
26	Correct	2219 ms	3260 KB	Output is correct
27	Correct	3 ms	1316 KB	Output is correct

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1275 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	461 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	553 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1842 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1688 KB	Output is correct
2	Correct	2 ms	1160 KB	Output is correct
3	Correct	3 ms	1316 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	5 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	87 ms	900 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	5 ms	640 KB	Output is correct
11	Correct	128 ms	912 KB	Output is correct
12	Correct	13 ms	880 KB	Output is correct
13	Correct	1 ms	516 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	82 ms	620 KB	Output is correct
16	Correct	2338 ms	2164 KB	Output is correct
17	Correct	97 ms	712 KB	Output is correct
18	Correct	860 ms	1160 KB	Output is correct
19	Correct	6 ms	596 KB	Output is correct
20	Correct	2252 ms	2244 KB	Output is correct
21	Correct	759 ms	1160 KB	Output is correct
22	Correct	3 ms	1668 KB	Output is correct
23	Correct	7 ms	516 KB	Output is correct
24	Correct	3 ms	1112 KB	Output is correct
25	Correct	2089 ms	2248 KB	Output is correct
26	Correct	2219 ms	3260 KB	Output is correct
27	Correct	3 ms	1316 KB	Output is correct
28	Runtime error	1275 ms	524288 KB	Execution killed with signal 9
29	Halted	0 ms	0 KB	-