QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112268 | #6563. Four Square | ITMO_pengzoo# | WA | 4ms | 3960kb | C++20 | 4.4kb | 2023-06-10 23:09:36 | 2023-06-10 23:09:39 |
Judging History
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;
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;
}
break;
}
}
return true;
}
void run() {
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: 1ms
memory: 3592kb
input:
1 1 1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
3 1 3 3 2 2 3 3
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 2ms
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: 3532kb
input:
5 3 5 5 3 3 3 5
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
1 2 4 8 16 32 64 128
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
4 4 2 1 4 4 2 1
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 4ms
memory: 3712kb
input:
995 51 559 565 154 536 56 780
output:
0
result:
ok single line: '0'
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 3960kb
input:
391 694 540 42 240 937 691 246
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'