QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207845#6563. Four SquareFreeuni1#WA 2ms3512kbC++141.5kb2023-10-08 21:26:592023-10-08 21:27:00

Judging History

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

  • [2023-10-08 21:27:00]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3512kb
  • [2023-10-08 21:26:59]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
int tot = 0;
vector<array<int, 2> > v;

int fit(vector<array<int, 2> > v, int s1, int s2, int bit) {
    for (int i = 0; i < (1 << (int)(v.size())); i ++) {
        if ((bit&i) != i) {
            continue;
        }
        int s = s2;
        for (int j = 0; j < v.size(); j ++) {
            if ((i & (1 << j)) && v[j][0] == s1) {
                s -= v[j][1];
            }
        }
        if (!s) return i;
        s = s1;
        for (int j = 0; j < v.size(); j ++) {
            if ((i & (1 << j)) && v[j][1] == s2) {
                s -= v[j][0];
            }
        }
        if (!s) return i;
    }
    return -1;
}

int ddi(vector<array<int, 2> > v, int s1, int s2, int bit) {
    if (s1*s2 == 0) {
        return 1;
    }
    for (int i = 1; i <= s1; i ++) {
        int bb = fit(v, i, s2, bit);
        if (bb != -1) {
            if (ddi(v, s1 - i, s2, bb^bit)) {
                return 1;
            }
        }
    }
    for (int i = 1; i <= s2; i ++) {
        int bb = fit(v, s1, i, bit);
        if (bb != -1) {
            if (ddi(v, s1, s2 - i, bb^bit)) {
                return 1;
            }
        }
    }
    return 0;
}

main() {
    for (int i = 0; i < 4; i ++) {
        int a, s;
        cin >> a >> s;
        v.push_back({a, s});
        tot += a * s;
    }

    int a = sqrt(tot);
    if (a*a != tot) {
        cout << 0;
        return 0;
    }

    cout << ddi(v, a, a, (1 << v.size()) - 1);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

score: -100
Wrong Answer
time: 2ms
memory: 3444kb

input:

1000 999
998 1000
997 1000
997 997

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'