QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140344#6563. Four Squaresmosp#AC ✓37ms18916kbC++172.4kb2023-08-15 18:58:492023-08-15 18:58:52

Judging History

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

  • [2023-08-15 18:58:52]
  • 评测
  • 测评结果:AC
  • 用时:37ms
  • 内存:18916kb
  • [2023-08-15 18:58:49]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;


// Source: ecnerwala
// Fast recursion with lambdas
// Use it like:
// auto f = y_combinator([](auto self,....)->return_type{...self(...)});
template <class Fun>
class y_combinator_result {
  Fun fun_;

 public:
  template <class T>
  explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

  template <class... Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

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

  vector<array<int,2>> sq(4);
  int64_t ar = 0;
  for (auto& a : sq) {
    for (auto& x : a) cin >> x;
    ar += a[0]*a[1];
  }

  int64_t side = 0;
  while(side*side < ar) side++;
  if (side*side != ar) {
    cout << 0;
    return 0;
  }

  vector<vector<int>> grid(side, vector<int>(side));
  auto check = [&](int lx, int rx, int ly, int ry)->bool {
    if (rx > side || ry > side) return false;
    for (int i = lx; i < rx; i++) {
      for (int j = ly; j < ry; j++) {
        if (grid[i][j]) return false;
      }
    }
    return true;
  };

  auto fill = [&](int lx, int rx, int ly, int ry, int c)->void {
    for (int i = lx; i < rx; i++) {
      for (int j = ly; j < ry; j++) {
        grid[i][j] = c;
      }
    }
  };

  bool ans = false;
  for (int m = 0; m < (1<<4) && !ans; m++) {
    for (int b = 0; b < 4;b++) {
      if (m>>b&1) swap(sq[b][0], sq[b][1]);
    }

    ans |= y_combinator([&](auto self, int taken)->bool {
      if (taken+1 == (1<<4)) return true;
      int x = -1, y = -1;
      for (int i = 0; i < side; i++) {
        if (x != -1) break;
        for (int j = 0; j < side; j++) {
          if (y != -1) break;
          if (!grid[i][j])
            x = i, y = j;
        }
      }
      assert(x != -1);

      for (int b = 0; b < 4; b++) {
        if (taken>>b&1) continue;
        if (check(x, x+sq[b][0], y, y+sq[b][1])) {
          fill(x, x+sq[b][0], y, y+sq[b][1], 1);
          if (self(taken^(1<<b))) return true;
          fill(x, x+sq[b][0], y, y+sq[b][1], 0);
        }
      }
      return false;
    })(0);

    for (int b = 0; b < 4;b++) {
      if (m>>b&1) swap(sq[b][0], sq[b][1]);
    }
  }
  
  cout << ans << '\n';
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

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: 5ms
memory: 5116kb

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 20ms
memory: 6184kb

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 5ms
memory: 4372kb

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 37ms
memory: 18904kb

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'