Submission #572037

#	Time	Username	Problem	Language	Result	Execution time	Memory
572037		grt	L-triominoes (CEOI21_ltriominoes)	C++17	100 / 100	1297 ms	14784 KiB

ltrominoes

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

int w, h, k;
vi g[(1 << 14)][14];
map<int, int>state;
int vis[(1 << 14)][14], cur;
int hsh[(1 << 14)];
vi masks;

void dfs(int mask, int row) {
	vis[mask][row] = cur;
	for(int m : g[mask][row]) {
		if(vis[m][row + 1] != cur) {
			dfs(m, row + 1);
		}
	}
}

map<int, vi>achieve;

void rozwaz(int ww) {
	cur++;
	int hs = 0;
	for(int m : masks) {
		hs ^= hsh[m];
	}
	vi good = {};
	if(achieve.count(hs)) {
		good = achieve[hs];
	} else {
		for(int m : masks) {
			if(vis[m << 1][0] != cur)
				dfs(m << 1, 0);
		}
		vi tmp = {};
		for(int i = 0; i < (1 << w); ++i) {
			if(vis[i << 1][w]==cur) {
				tmp.PB(i);
			}
		}
		achieve[hs] = tmp;
		good = tmp;
	}
	masks = {};
	for(int i : good) {
		if((i & ww) == ww) {
			masks.PB(i ^ ww);
		}
	}
}

int period[13] = {0, 3, 2, 3, 6, 6, 6, 3, 20, 3, 6, 6, 6};

void zeroes(int cnt) {
	int ile = 0;
	for(int i = 0; i < min(12, cnt); ++i) {
		rozwaz(0);
		ile++;
	}
	cnt -= ile;
	cnt %= period[w - 1];
	for(int i = 0; i < cnt; ++i) {
		rozwaz(0);
	}
}

mt19937 rng(19024910);

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> w >> h >> k;
	for(int i = 0; i < (1 << w); ++i) hsh[i] = rng() % 1000000000;
	for(int row = 0; row < w; ++row) {
		for(int mask = 0; mask < (1 << (w + 1)); ++mask) {
			if((mask & 1) == 0) g[mask][row].PB((mask >> 1) | (1 << w));
			int m = (mask >> 1);
			if(row < w - 1) {
				if((m&3)==3 && (mask & 1) == 0) {
					g[mask][row].PB(m^3);
				}
			}
			if(row > 0) {
				if((m&1) && (m & (1 << (w-1))) && (mask & 1) == 0) {
					m ^= 1;
					m ^= (1 << (w - 1));
					g[mask][row].PB(m);
					m ^= 1;
					m ^= (1 << (w - 1));
				}
			}
			if(row > 0) {
				if((mask & 3)==3) {
					g[mask][row].PB((mask^3) >> 1);
				}
			}
			if(row > 0) {
				if((mask & 1) && (mask & (1 << w))) {
					g[mask][row].PB((mask^1^(1<<w))>>1);
				}
			}
		}
	}
	for(int x, y, i = 0; i < k; ++i) {
		cin >> x >> y;
		state[y] += (1 << ((x - 1)));
	}
	masks = {0};
	int last = 0;
	for(auto it : state) {
		int cnt = it.ST - last - 1;
		zeroes(cnt);
		rozwaz(it.ND);
		last = it.ST;
	}
	int cnt = h - last;
	if(cnt > 0) zeroes(cnt);
	bool exist = false;
	for(int m : masks) if(!m) exist = true;
	if(!exist) cout << "NO";
	else cout << "YES";
	
}

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20