Submission #577435

#	Time	Username	Problem	Language	Result	Execution time	Memory
577435		amunduzbaev	L-triominoes (CEOI21_ltriominoes)	C++17	11 / 100	753 ms	4844 KiB

ltrominoes

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll
 
struct mtx{
	vector<vector<int>> t;
	int n;
	
	mtx (int sz){
		n = sz;
		t.resize(n, vector<int>(n, 0));
	}
	
	mtx operator * (mtx& b){
		mtx c(n);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					c.t[i][j] |= (t[i][k] & b.t[k][j]);
				}
			}
		} return c;
	}
};

void solve(int n, int m, int k){
	vector<ar<int, 2>> a(k);
	for(int i=0;i<k;i++){
		cin>>a[i][0]>>a[i][1];
		a[i][0]--, a[i][1]--;
	}
	
	vector<mtx> pw(30, mtx(1 << n));
	{
		mtx dp(1 << n);
		for(int i=0;i < (1 << n);i++){
			for(int j=0;j < (1 << (n + n));j++){
				int mask = 0, mm = i;
				for(int l=0;l<n;l++){
					if(mm >> l & 1) continue;
					int v = (j >> (2 * l)) & 3;
					if(v == 0){
						if(l + 1 < n && !(mm >> (l + 1) & 1) && !(mask >> (l + 1) & 1)){
							mm |= (1 << l);
							mm |= (1 << (l + 1));
							mask |= (1 << (l + 1));
						}
					}
					if(v == 1){
						if(l + 1 < n && !(mm >> (l + 1) & 1) && !(mask >> l & 1)){
							mm |= (1 << l);
							mm |= (1 << (l + 1));
							mask |= (1 << l);
						}
					}
					if(v == 2){
						if(l && !(mask >> (l - 1) & 1) && !(mask >> l & 1)){
							mm |= (1 << l);
							mask |= (1 << l);
							mask |= (1 << (l - 1));
						}
					}
					if(v == 3){
						if(l + 1 < n && !(mask >> (l + 1) & 1) && !(mask >> l & 1)){
							mm |= (1 << l);
							mask |= (1 << l);
							mask |= (1 << (l + 1));
						}
					}
				}
				
				if(mm == (1 << n) - 1 && !dp.t[i][mask]){
					//~ for(int j=0;j<n;j++) cout<<(i >> j & 1);
					//~ cout<<endl;
					//~ for(int j=0;j<n;j++) cout<<(mask >> j & 1);
					//~ cout<<endl<<endl;
					dp.t[i][mask] = 1;
				}
			}
		}
		
		pw[0] = dp;
		for(int j=1;j<30;j++){
			pw[j] = pw[j-1] * pw[j-1];
		}
	}
	
	sort(a.begin(), a.end(), [&](auto& a, auto& b){
		return (a[1] < b[1]);
	});
	
	vector<int> dp(1 << n);
	dp[(1 << n) - 1] = 1;
	int last = -1;
	for(int i=0;i<k;){
		int j = i, rev = 0;
		while(j<k && a[j][1] == a[i][1]) rev |= (1 << a[j][0]), j++;
		
		int d = a[i][1] - last;
		//~ cout<<d<<endl;
		//~ for(int i=0;i<n;i++) cout<<(rev >> i & 1);
		//~ cout<<endl;
		for(int l=29;~l;l--){
			if(d >> l & 1){
				d ^= (1 << l);
				vector<int> tp(1 << n);
				for(int mask=0;mask < (1 << n);mask++){
					for(int j=0;j < (1 << n);j++){
						if(d){
							tp[j] |= (dp[mask] & pw[l].t[mask][j]);
						} else {
							if(j & rev) continue;
							//~ if(dp[mask] && pw[l].t[mask][j]){
								//~ for(int i=0;i<n;i++) cout<<(mask >> i & 1);
								//~ cout<<endl;
								//~ for(int i=0;i<n;i++) cout<<(j >> i & 1);
								//~ cout<<endl;
							//~ }
							tp[j | rev] |= (dp[mask] & pw[l].t[mask][j]);
						}
					}
				}
				swap(tp, dp);
			}
		} last = a[i][1], i = j;
	}
	
	int d = m - last - 1;
	for(int l=29;~l;l--){
		if(d >> l & 1){
			vector<int> tp(1 << n);
			for(int mask=0;mask < (1 << n);mask++){
				for(int j=0;j < (1 << n);j++){
					tp[j] |= dp[mask] & pw[l].t[mask][j];
				}
			}
			
			swap(tp, dp);
		}
	}
	
	if(dp[(1 << n) - 1]) cout<<"YES\n";
	else cout<<"NO\n";
}

const int N = 13;
vector<int> edges[1 << N];
int dp[2][N][1 << (N + 1)], is[N][2];

void solve2(int n, int m = 2){
	for(int M=0;M < (1 << n);M++){
		memset(is, 0, sizeof is);
		memset(dp, 0, sizeof dp);
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				is[i][j] = 1;
			}
		}
		
		for(int i=0;i<n;i++){
			is[i][0] = !(M >> i & 1);
		}
		int ch[4][2] = {
			{0, 0},
			{-1, 0},
			{-1, 1},
			{0, 1} 
		};
		int P[4] = {1, 0, -1, 0}, mas[4] = {14, 13, 11, 7};
		int mask = (!is[0][1]);
		for(int i=0;i<n;i++){
			if(!is[i][0]) mask |= (1 << (i + 1));
		}
		
		dp[0][1][mask] = 1;
		for(int i=0;i+1<m;i++){
			int c = i&1;
			memset(dp[!c], 0, sizeof dp[!c]);
			for(int j=1;j<n;j++){
				for(int mask=0;mask < (1 << (n + 1));mask++){
					if(!dp[c][j][mask]) continue;
					int us = 0;
					for(int t=0;t<4;t++){
						us |= (is[j + ch[t][0]][i + ch[t][1]] & (t < 3 ? !(mask >> (j + P[t]) & 1) : 1)) << t;
					}
					
					for(int t=0;t<4;t++){
						if((us & mas[t]) != mas[t]) continue;
						int m2 = mask;
						for(int l=0;l<4;l++){
							if(mas[t] >> l & 1){
								//~ assert(!(m2 >> (j + P[l]) & 1));
								m2 |= (1 << (j + P[l]));
							}
						}
						if(t == 1 && !(mask >> j & 1)) continue;
						if(t == 3){
							m2 ^= (1 << j);
							m2 |= (!is[j][i + 1]) << j;
						}
						
						if(j + 1 < n){
							dp[c][j + 1][m2] = 1;
						} else if(m2 >> n & 1) {
							m2 ^= (1 << n);
							m2 = m2 << 1 | (!is[0][i + 2]);
							
							//~ cout<<j<<" "<<i<<" "<<mask<<" "<<m2<<"\n";
							//~ for(int i=0;i<=n;i++){
								//~ cout<<(mask >> i & 1);
							//~ } cout<<"\n";
							
							//~ for(int i=0;i<=n;i++){
								//~ cout<<(m2 >> i & 1);
							//~ } cout<<"\n";
							
							dp[!c][1][m2] = 1;
						}
					}
					
					if(mask >> j & 1){
						int m2 = mask;
						if(j + 1 < n){
							m2 ^= (1 << j);
							m2 |= (!is[j][i+1]) << j;
							dp[c][j + 1][m2] = 1;
						} else if(m2 >> n & 1) {
							m2 ^= (1 << j) ^ (1 << n);
							m2 |= (!is[j][i+1]) << j;
							m2 = m2 << 1 | (!is[0][i + 2]);
							//~ cout<<j<<" "<<i<<" "<<mask<<" "<<m2<<"\n";
							//~ for(int i=0;i<=n;i++){
								//~ cout<<(mask >> i & 1);
							//~ } cout<<"\n";
							
							//~ for(int i=0;i<=n;i++){
								//~ cout<<(m2 >> i & 1);
							//~ } cout<<"\n";
							dp[!c][1][m2] = 1;
						}
					}
				}
			}
		}
		
		for(int m2=0;m2<(1 << (n + 1));m2++){
			//~ cout<<m2<<" "<<dp[(m - 1)&1][1][m2]<<"\n";
			if(dp[(m-1)&1][1][m2]){
				edges[M].push_back((m2 >> 1));
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m, k; cin>>n>>m>>k;
	if(n <= 3){
		solve(n, m, k);
		return 0;
	}
	
	vector<int> x(k), y(k), p(k);
	for(int i=0;i<k;i++){
		cin>>x[i]>>y[i];
		x[i]--, y[i]--;
		p[i] = i;
	}
	for(int i=0;i<n;i++){
		x.push_back(i);
		y.push_back(m);
		p.push_back(i + k);
	}
	k += n;
	sort(p.begin(), p.end(), [&](int i, int j){
		if(y[i] != y[j]) return y[i] < y[j];
		return x[i] < x[j];
	});
	vector<int> M, m2[3];
	for(int mask=0;mask < (1 << n);mask++){
		int b = __builtin_popcount(mask);
		if(n&1){
			int is = (mask & 1);
			for(int i=1;i<n;i+=2){
				is &= (!(mask >> i & 1) && (mask >> (i + 1)));
			}
			
			if(is) continue;
		}
		m2[b % 3].push_back(mask);
	}
	
	solve2(n);
	int used[1 << N] {};
	auto get = [&](vector<int> M, int m, int ban){
		for(int c=0;c<m;c++){
			memset(used, 0, sizeof used);
			queue<int> qq;
			for(auto x : M){
				qq.push(x);
			}
			M.clear();
			while(!qq.empty()){
				int u = qq.front(); qq.pop();
				for(auto x : edges[u]){
					if(used[x]) continue;
					used[x] = 1;
					M.push_back(x);
				}
			}
		}
		vector<int> tt;
		for(auto x : M){
			if(x & ban) continue;
			tt.push_back(x | ban);
		}
		return tt;
	};
	
	M.push_back((1 << n) - 1);
	int last = -1, cur = n % 3;
	for(int i=0,j=0;i<k && !M.empty(); i = j){
		int mask = 0;
		while(j < k && y[p[j]] == y[p[i]]) mask |= (1 << x[p[j]]), j++;
		int d = (__builtin_popcount(M.back()) + (3 - n % 3) % 3 * (y[p[i]] - last)) % 3;
		if(y[p[i]] - last <= 11){
			M = get(M, y[p[i]] - last + 1, mask);
		} else {
			M = m2[(cur + d) % 3];
		}
		cur = (cur + d) % 3;
		last = y[p[i]];
	}
	if(!M.empty()) cout<<"YES\n";
	else cout<<"NO\n";
}

Compilation message (stderr)

ltrominoes.cpp: In function 'void solve2(ll, ll)':
ltrominoes.cpp:209:36: warning: array subscript 2 is above array bounds of 'll [2]' {aka 'long int [2]'} [-Warray-bounds]
  209 |        m2 = m2 << 1 | (!is[0][i + 2]);
      |                         ~~~~~~~~~~~^
ltrominoes.cpp:233:36: warning: array subscript 2 is above array bounds of 'll [2]' {aka 'long int [2]'} [-Warray-bounds]
  233 |        m2 = m2 << 1 | (!is[0][i + 2]);
      |                         ~~~~~~~~~~~^

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