QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#359410#6563. Four Squarenkamzabek#AC ✓1ms3888kbC++231.9kb2024-03-20 17:37:362024-03-20 17:37:37

Judging History

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

  • [2024-03-20 17:37:37]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3888kb
  • [2024-03-20 17:37: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, dep;

void calc(vector<pair<int, int> > v, int msk){
	if(v.empty()){
		cout << "1\n";
		exit(0);
	}
	

    for(auto i = 0; i < sz(v); i++){
		for(int j = 0; j < 4; j++){
			if(msk >> j & 1)
				continue;
			int x = v[i].f, y = v[i].s;
			if(x + h[j] <= sq && y + w[j] <= sq){
				vector<pair<int, int> > nxt;
				for(auto [xx, yy] : v){
					if(x <= xx && xx <= x + h[j] && y <= yy && yy <= y + w[j]) continue;
					nxt.push_back({xx, yy});
				}
				
				if(x + h[j] < sq){
					nxt.push_back({x + h[j], y});
				}	
				if(y + w[j] < sq){
					nxt.push_back({x, y + w[j]});
				}
				if(x + h[j] < sq && y + w[j] < sq){
					nxt.push_back({x + h[j], y + w[j]});
				}
				calc(nxt, msk | (1 << j));
			}

			if(x + w[j] <= sq && y + h[j] <= sq){
				vector<pair<int, int> > nxt;
				for(auto [xx, yy] : v){
					if(x <= xx && xx <= x + w[j] && y <= yy && yy <= y + h[j]) continue;
					nxt.push_back({xx, yy});
				}
				
				if(x + w[j] < sq){
					nxt.push_back({x + w[j], y});
				}	
				if(y + h[j] < sq){
					nxt.push_back({x, y + h[j]});
				}
				if(x + w[j] < sq && y + h[j] < sq){
					nxt.push_back({x + w[j], y + h[j]});
				}
				calc(nxt, msk | (1 << j));
			} 
		}
	}

}
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, 0}}, 0);	
	
	cout << "0\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

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: 0ms
memory: 3648kb

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'