oj.uz

Submission #539003

# Submission time Handle Problem Language Result Execution time Memory
539003 2022-03-18T07:52:00 Z amunduzbaev L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 53 ms 2516 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

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][j] | b.t[i][j]);
				}
			}
		} return c;
	}
};

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m, k; cin>>n>>m>>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);j++){
				int mask = 0, mm = i;
				for(int l=0;l<n;l++){
					if(mm >> l & 1) continue;
					mm |= (1 << l);
					if(l + 1 < n && !(mm >> (l + 1) & 1) && !(mask >> (l + (j >> l & 1)) & 1) && 
					(j >> l & 1) == (j >> (l + 1) & 1)){
						mm |= (1 << (l + 1));
						mask |= (1 << (l + (j >> l & 1)));
					} else if((j >> l & 1) && l + 1 < n && !(mask >> (l + 1) & 1) && !(mask >> l & 1)){
						mask |= (1 << l);
						mask |= (1 << (l + 1));
					} else if(!(j >> l & 1) && l && !(mask >> (l - 1) & 1) && !(mask >> l & 1)){
						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;
		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;
							tp[j | rev] |= dp[mask] & pw[l].t[mask][j];
						}
					}
				}
				swap(tp, dp);
			}
		} last = a[i][1], i = j;
	}
	
	if(!k){
		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";
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 2 ms 448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 2 ms 448 KB Output isn't correct
7 Halted 0 ms 0 KB -