QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110869#6563. Four SquareHe_Ren#AC ✓9ms4076kbC++171.4kb2023-06-04 14:16:422023-06-04 14:16:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-04 14:16:46]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:4076kb
  • [2023-06-04 14:16:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e3 + 5;

#define bbit(i) (1<<(i))
#define bdig(x,i) (((x)>>(i))&1)

const int n = 4;

int d;
array<int,2> a[n+1];

using Data = bitset<MAXN>;

Data b[MAXN];

Data getData(int l,int r)
{
	Data res;
	res.set();
	return (res >> (MAXN - (r-l+1))) << l;
}

bool check(void)
{
	for(int i=0; i<d; ++i)
		b[i].set();
	
	for(int i=1,x=0; i<=n; ++i)
	{
		int y = -1;
		while(x<d && (y = b[x]._Find_first()) >= d)
			++x;
		
		if(x + a[i][0] - 1 >= d || y + a[i][1] - 1 >= d)
			return 0;
		
		Data cur = getData(y, y + a[i][1] - 1);
		
		for(int j=x; j<x+a[i][0]; ++j)
		{
			if((int)(b[j] & cur).count() != a[i][1]) return 0;
			b[j] ^= cur;
		}
	}
	return 1;
}

int main(void)
{
	for(int i=1; i<=n; ++i)
		scanf("%d%d",&a[i][0], &a[i][1]);
	
	int sum = 0;
	for(int i=1; i<=n; ++i)
		sum += a[i][0] * a[i][1];
	
	d = sqrt(sum) + 5;
	while(d * d > sum) --d;
	if(d * d != sum)
	{
		printf("0\n");
		return 0;
	}
	
	sort(a+1, a+n+1);
	do
	{
		for(int mask=0; mask<(1<<n); ++mask)
		{
			for(int i=1; i<=n; ++i) if(bdig(mask, i-1))
				swap(a[i][0], a[i][1]);
			
			if(check())
			{
				printf("1\n");
				return 0;
			}
			
			for(int i=1; i<=n; ++i) if(bdig(mask, i-1))
				swap(a[i][0], a[i][1]);
		}
	}while(next_permutation(a+1, a+n+1));
	
	printf("0\n");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3536kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3684kb

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3612kb

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 7ms
memory: 3920kb

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 9ms
memory: 3704kb

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 8ms
memory: 3760kb

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 6ms
memory: 3676kb

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3748kb

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 3ms
memory: 4040kb

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 2ms
memory: 4076kb

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3616kb

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'