QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#152691#6563. Four SquareBUET_POISSON#AC ✓3916ms3776kbC++202.3kb2023-08-28 17:25:262023-08-28 17:25:27

Judging History

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

  • [2023-08-28 17:25:27]
  • 评测
  • 测评结果:AC
  • 用时:3916ms
  • 内存:3776kb
  • [2023-08-28 17:25:26]
  • 提交

answer

#include <bits/stdc++.h>
 
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
#define int long long
#define ii pair<int, int>

#define ll long long 
#define lll __int128_t
#define pb push_back

bool put(vector<vector<bool>> &grid, int w, int h) {
    int n = grid.size();
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if ( grid[i][j] == 0 and i+w-1 < n and j+h-1 < n ) {
                //cout << "Placing at " << i << " " << j << endl; 
                for (int k=0; k<w; k++) for (int m=0; m<h; m++) grid[i+k][j+m] = 1;
                return true;
            }
        }
    }
    return false;
}

void solve() {
    vector<ii> planes;
    int tot_area = 0;
    for (int i=0; i<4; i++) {
        int a, b;
        cin >> a >> b;
        planes.pb({a, b});
        tot_area += a*b;
    }

    int s = sqrt(tot_area);
    if ((s+1)*(s+1) == tot_area) s++;
    if (s * s!= tot_area) {
        cout << 0 << endl;
        return;
    }

    vector<int> order = {0, 1, 2, 3};

    int possible = 0;
    int loop = 0;
    do {
        
        for (int i=0; i<(1<<4); i++) {
            vector<ii> a;
            for (int x: order) a.push_back(planes[x]);
            for (int j=0; j<4; j++) if ( (i>>j) & 1) {
                swap(a[j].first, a[j].second);
            }
            vector< vector<bool> > arr(s, vector<bool> (s));
            int pos = 1;
            for (int j=0; j<4; j++) if (!put(arr, a[j].first, a[j].second)) {
                //cout << "Couldnt place " << j << " " << a[j].first << " " << a[j].second << endl;
                pos = 0;
            }
            
            for (int i=0; i<s; i++) for (int j=0; j<s; j++) if (arr[i][j] == false) pos = 0;

           
                

            if (pos) possible = 1;

            //return ;
        }
        
    } while(next_permutation(order.begin(), order.end()));
    cout << possible << endl;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    
    solve();
    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3436kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 427ms
memory: 3516kb

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 535ms
memory: 3664kb

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 593ms
memory: 3556kb

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 3916ms
memory: 3776kb

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'