QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112270#6563. Four SquareITMO_pengzoo#AC ✓14ms4092kbC++204.6kb2023-06-10 23:23:382023-06-10 23:23:41

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-10 23:23:41]
  • 评测
  • 测评结果:AC
  • 用时:14ms
  • 内存:4092kb
  • [2023-06-10 23:23:38]
  • 提交

answer

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <stdio.h>
#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}

template<size_t index, typename T>
std::ostream& print_tuple(std::ostream& out, const T& t) {
    if constexpr (index == std::tuple_size<T>::value) {
        out << ")";
        return out;
    } else {
        if (index > 0) {
            out << ", ";
        } else {
            out << "(";
        }
        out << std::get<index>(t);
        return print_tuple<index + 1, T>(out, t);
    }
}

template<typename ...T>
std::ostream& operator<<(std::ostream& out, const std::tuple<T...>& t) {
    return print_tuple<0, std::tuple<T...>>(out, t);
}

template<typename Container, typename = decltype(std::begin(std::declval<Container>()))>
typename std::enable_if<!std::is_same<Container, std::string>::value, std::ostream&>::type
operator<<(std::ostream& out, const Container& container) {
    out << "{";
    for (auto it = container.begin(); it != container.end(); ++it) {
        if (it != container.begin()) {
            out << ", ";
        }
        out << *it;
    }
    out << "}";
    return out;
}

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

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

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int SZ = 2010;

std::bitset<SZ> field[SZ];
std::bitset<SZ> cur;
std::pair<int, int> a[4];
int perm[4];
int side;


bool check() {
	for (int i = 0; i < side; ++i) {
		field[i].reset();
	}

	for (int i = 0; i < 4; ++i) {
		int id = perm[i];
		int x = a[id].first;
		int y = a[id].second;

		bool isGood = false;
		for (int row = 0; row + x - 1 < side; ++row) {
			int pos = (~field[row])._Find_first();
			if (pos == side) {
				continue;
			}
			if (pos + y - 1 >= side) {
				return false;
			}

			cur.reset();
			for (int j = pos; j < pos + y; ++j) {
				cur[j] = true;
			}

			for (int j = row; j < row + x; ++j) {
				if ((cur & field[j]).count() > 0) {
					return false;
				}
				field[j] |= cur;
			}
			isGood = true;
			break;
		}

		if (!isGood) {
			return false;
		}
	}

	return true;
}

void run() {
	// for (int ss = 1; ss <= 2000; ++ss) {
	// 	int sq = ss * ss;
	// 	assert((int)sqrtl(sq) == ss);
	// }
	int totalSquare = 0;
    for (int i = 0; i < 4; ++i) {
    	scanf("%d%d", &a[i].first, &a[i].second);
    	totalSquare += a[i].first * a[i].second;
    }

    side = (int)sqrtl(totalSquare);
    if (side * side != totalSquare) {
    	printf("0\n");
    	return;
    }

    for (int i = 0; i < 4; ++i) {
    	perm[i] = i;
    }

    do {
    	for (int i1 = 0; i1 < 2; ++i1) {
    		for (int i2 = 0; i2 < 2; ++i2) {
    			for (int i3 = 0; i3 < 2; ++i3) {
    				for (int i4 = 0; i4 < 2; ++i4) {
    					if (check()) {
    						printf("1\n");
    						return;
    					}
    					std::swap(a[3].first, a[3].second);
    				}
    				std::swap(a[2].first, a[2].second);
    			}
    			std::swap(a[1].first, a[1].second);
    		}
    		std::swap(a[0].first, a[0].second);
    	}
    } while (std::next_permutation(perm, perm + 4));

    printf("0\n");
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    #ifdef PERVEEVM_LOCAL
        auto start = std::chrono::high_resolution_clock::now();
    #endif

    run();

    #ifdef PERVEEVM_LOCAL
        auto end = std::chrono::high_resolution_clock::now();
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3680kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 11ms
memory: 3844kb

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 14ms
memory: 3964kb

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'