QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#240968#6563. Four SquareMovingUp#AC ✓15ms66180kbC++171.9kb2023-11-05 21:26:062023-11-05 21:26:06

Judging History

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

  • [2023-11-05 21:26:06]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:66180kb
  • [2023-11-05 21:26:06]
  • 提交

answer

#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int MAX_LEN = 4000;

struct rect {
  int w, h;
};

bool foundSolution = false;
int board[MAX_LEN][MAX_LEN];
int len;
vector<rect> rects;

bool tryFit(int w, int h, int i, int j, int r) {
  if (i + h > len || j + w > len)
    return false;

  for (int a = 0; a < h; a++) {
    for (int b = 0; b < w; b++) {
      if (board[i + a][b + j] != -1)
        return false;

      board[i + a][b + j] = r;
    }
  }

  return true;
}

void unfit(int w, int h, int i, int j, int r) {
  if (i + h > len || j + w > len)
    return;

  for (int a = 0; a < h; a++) {
    for (int b = 0; b < w; b++) {
      if (board[i + a][b + j] == r)
        board[i + a][b + j] = -1;
    }
  }
}

void bruteForce(int mask) {
  if (mask == (1 << 4) - 1) {
    foundSolution = true;
    return;
  }
  if (foundSolution)
    return;

  int i, j;
  bool found = false;
  for (i = 0; i < len; i++) {
    for (j = 0; j < len; j++) {
      if (board[i][j] == -1) {
        found = true;
        break;
      }
    }
    if (found)
      break;
  }

  for (int r = 0; r < 4; r++) {
    if ((mask & (1 << r)) == 0) {
      bool fit = tryFit(rects[r].w, rects[r].h, i, j, r);
      if (fit)
        bruteForce(mask | (1 << r));
      unfit(rects[r].w, rects[r].h, i, j, r);

      fit = tryFit(rects[r].h, rects[r].w, i, j, r);
      if (fit)
        bruteForce(mask | (1 << r));
      unfit(rects[r].h, rects[r].w, i, j, r);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  rects.resize(4);

  int area = 0;
  for (int i = 0; i < 4; i++) {
    cin >> rects[i].w >> rects[i].h;
    area += rects[i].w * rects[i].h;
  }

  len = sqrt(area);
  if (len * len != area) {
    cout << 0 << endl;
    return 0;
  }

  memset(board, -1, sizeof(board));
  bruteForce(0);

  cout << foundSolution << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 4ms
memory: 66108kb

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 15ms
memory: 66128kb

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 4ms
memory: 66108kb

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

score: 0
Accepted
time: 4ms
memory: 66120kb

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'