QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111069#6563. Four SquareKhNURE_KIVI#AC ✓8ms3704kbC++233.6kb2023-06-05 18:50:312023-06-05 18:50:33

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-05 18:50:33]
  • 评测
  • 测评结果:AC
  • 用时:8ms
  • 内存:3704kb
  • [2023-06-05 18:50:31]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int a[4], b[4];
bool u[4];

vector<array<int, 4> > on;

int side = 0;

void go(int x, int y) {
    if(x == side) {
        if(y == side - 1) return;
        go(0, y + 1);
    }
    bool bad = false;
    for(auto& cr : on)
        bad |= (cr[0] <= x && x <= cr[1] && cr[2] <= y && y <= cr[3]);
    if(bad) go(x + 1, y);
    else {
        for(int to_use = 0; to_use < 4; to_use++) {
            if(u[to_use]) continue;
            for(int it = 0; it < 2; it++) {
                int x1 = x, y1 = y;
                int x2 = x1 + a[to_use] - 1;
                int y2 = y1 + b[to_use] - 1;
                bool bad_use = (x2 >= side || y2 >= side);
                for(auto& cr : on) {
                    int mnx = max(x1, cr[0]), mxx = min(x2, cr[1]);
                    int mny = max(y1, cr[2]), mxy = min(y2, cr[3]);
                    bad_use |= (mnx <= mxx && mny <= mxy);
                }
                if(!bad_use) {
                    u[to_use] = true;
                    on.pb({x1, x2, y1, y2});
                    if(len(on) == 4) {
                        cout << "1\n";
                        exit(0);
                    }
                    go(x + 1, y);
                    on.pop_back();
                    u[to_use] = false;
                }
                swap(a[to_use], b[to_use]);
            }
        }
    }
}

void solve() {
    int sum = 0;
    for(int i = 0; i < 4; i++) {
        cin >> a[i] >> b[i];
        sum += a[i] * b[i];
    }
    while(side * side < sum) side++;
    if(side * side != sum) { cout << "0\n"; return; }
    go(0, 0);
    cout << "0\n";
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

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: 2ms
memory: 3432kb

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'