QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#359381#6563. Four Squarenkamzabek#TL 12ms3732kbC++231.7kb2024-03-20 17:11:362024-03-20 17:11:36

Judging History

你现在查看的是最新测评结果

  • [2024-03-20 17:11:36]
  • 评测
  • 测评结果:TL
  • 用时:12ms
  • 内存:3732kb
  • [2024-03-20 17:11:36]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define sz(s) (int)s.size()
#define int long long

using namespace std;

const int N = (int)5e5 + 100;
const int M = N + 7;
const int MOD = 998244353;
const int INF = (int)1e18 + 100;


int n, w[4], h[4], a[N], sq;

void calc(int msk){
    if(msk == 15){
    	cout << "1\n";
    	exit(0);
    }
	for(int i = 0; i < sq; i++){
		for(int j = 0; j < 4; j++){
			if(msk >> j & 1){
				continue;
			}
			if(a[i] + w[j] <= sq && i + h[j] <= sq){
				int l = a[i], r = a[i] + w[j];
				bool bad = 0;
				for(int k = i; k < i + h[j]; k++){
					if(a[k] != l){
						bad = 1;
						break;
					}
				}
				            
				if(!bad){
					for(int k = i; k < i + h[j]; k++){
						a[k] = r;
					}
					calc(msk | (1 << j));
                	
                	for(int k = i; k < i + h[j]; k++){
						a[k] = l;
					}
				}
			}
			
			if(a[i] + h[j] <= sq && i + w[j] <= sq){
				int l = a[i], r = a[i] + h[j];
				bool bad = 0;
				for(int k = i; k < i + w[j]; k++){
					if(a[k] != l){
						bad = 1;
						break;
					}
				}               
				if(!bad){
					for(int k = i; k < i + w[j]; k++){
						a[k] = r;
					}
					calc(msk | (1 << j));
                	for(int k = i; k < i + w[j]; k++){
						a[k] = l;
					}
				}
			}
		}
	}	
}
main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	n = 4;
	int s = 0;
	for(int i = 0; i < 4; i++){
		cin >> w[i] >> h[i];    
		s += w[i] * h[i];
	}                     
	sq = 1;
	while((sq + 1) * (sq + 1) <= s)
		sq++;                      
	if(sq * sq != s){
		cout << "0\n";
		return 0;
	}

	calc(0);	
	
	cout << "0\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 12ms
memory: 3732kb

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

score: -100
Time Limit Exceeded

input:

391 694
540 42
240 937
691 246

output:


result: