Submission #572036

#TimeUsernameProblemLanguageResultExecution timeMemory
572036grtL-triominoes (CEOI21_ltriominoes)C++17
45 / 100
8077 ms12336 KiB
#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);
		}
	}
}

unordered_map<int,int>was;

int rozwaz(int ww) {
	cur++;
	for(int m : masks) {
		if(vis[m << 1][0] != cur)
			dfs(m << 1, 0);
	}
	masks.clear();
	int hs = 0;
	for(int i = 0; i < (1 << w); ++i) {
		if(vis[(i << 1)][w]==cur && (i & ww) == ww) {
			masks.PB(i ^ ww);
			hs ^= hsh[i  ^ ww];
		}
	}
	return hs;
}

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

void zeroes(int cnt) {
	was.clear();
	int pr = 0;
	int ile = 0;
	for(int i = 0; i < min(12, cnt); ++i) {
		int hs = rozwaz(0);
		ile++;
		if(was.count(hs)) {
			pr = i - was[hs];
			break;
		}
		was[hs] = i;
	}
	cnt -= ile;
	if(pr != 0) cnt %= pr;
	else 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";
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...