QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#707344 | #6563. Four Square | tassei903# | AC ✓ | 96ms | 4192kb | C++23 | 4.0kb | 2024-11-03 15:35:08 | 2024-11-03 15:35:08 |
Judging History
answer
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define rep(i, l, r) for (int i = l; i < (r); i++)
#define all(x) begin(x), end(x)
using ll = long long;
using vi = vector<int>;
const ll INF = numeric_limits<ll>::max() / 100;
struct MCMF{
struct edge {
int from, to, rev;
ll cap, cost, flow;
};
int N;
vector<vector<edge>> ed;
vi seen;
vector<ll> dist, pi;
vector<edge*> par;
MCMF(int N) : N(N), ed(N), seen(N), dist(N), pi(N), par(N) {}
void addEdge(int from, int to, ll cap, ll cost) {
if (from == to) return;
ed[from].push_back(edge{ from, to, sz(ed[to]), cap, cost, 0});
ed[to].push_back(edge{to, from, sz(ed[from])-1, 0, -cost, 0});
}
void path(int s) {
fill(all(seen), 0);
fill(all(dist), INF);
dist[s] = 0; ll di;
__gnu_pbds::priority_queue<pair<ll, int>> q;
vector<decltype(q)::point_iterator> its(N);
q.push({0, s});
while (!q.empty()) {
s = q.top().second; q.pop();
seen[s] = 1; di = dist[s] + pi[s];
for (edge& e : ed[s]) if (!seen[e.to]) {
ll val = di - pi[e.to] + e.cost;
if (e.cap - e.flow > 0 && val < dist[e.to]) {
dist[e.to] = val;
par[e.to] = &e;
if (its[e.to] == q.end()) {
its[e.to] = q.push({-dist[e.to], e.to});
}
else {
q.modify(its[e.to], {-dist[e.to], e.to});
}
}
}
}
rep(i,0,N) pi[i] = min(pi[i] + dist[i], INF);
}
pair<ll, ll> maxflow(int s, int t) {
ll totflow = 0, totcost = 0;
while (path(s), seen[t]) {
ll fl = INF;
for (edge* x = par[t]; x; x = par[x->from]) {
fl = min(fl, x->cap - x->flow);
}
totflow += fl;
for(edge* x = par[t]; x; x = par[x->from]) {
x->flow += fl;
ed[x->to][x->rev].flow -= fl;
}
}
rep(i, 0, N)for(edge& e : ed[i]) totcost += e.cost * e.flow;
return {totflow, totcost/2};
}
};
bool is_prime(ll x) {
for (ll a = 2; a * a <= x; a++) {
if (x % a == 0)return 0;
}
return 1;
}
const unsigned long long inf = 1e18 + 2;
unsigned long long safe_pow(unsigned long long x, int e) {
unsigned long long a = 1;
rep(_, 0, e) {
if (a > inf / x)return -1;
a *= x;
}
return a;
}
using pii = pair<int, int>;
int main() {
int n = 4;
vector<pii> p(n);
rep(i, 0, n)cin >> p[i].first >> p[i].second;
int s = 0;
rep(i, 0, 4)s += p[i].first * p[i].second;
int m = -1;
rep(i, 1, 10000) {
if (i * i == s) {
m = i;
}
}
if (m == -1) {
cout << 0 << endl;
return 0;
}
vector<vector<bool>> used(m, vector<bool>(m));
int bit = 0;
auto find = [&]->pii{
rep(i, 0, m)rep(j, 0, m)if(!used[i][j])return {i, j};
};
auto check = [&](int x, int y, int h, int w)->bool {
rep(i, x, x+h)rep(j, y, y+w)if(i >= m || j >= m || used[i][j])return 0;
return 1;
};
auto flip = [&](int x, int y, int h, int w)->void {
rep(i, x, x+h)rep(j, y, y+w)used[i][j]=!used[i][j];
};
vi idx(4);iota(all(idx), 0);
bool flag = 0;
auto dfs = [&](auto self)->void {
if (flag)return;
if (bit == (1<<n) - 1) {flag = 1;return;}
// cout << bit << endl;
rep(i, 0, n) {
if (bit >> i & 1)continue;
auto [x, y] = find();
bit ^= (1 << i);
if (check(x, y, p[i].first, p[i].second)) {
flip(x, y, p[i].first, p[i].second);
self(self);
flip(x, y, p[i].first, p[i].second);
}
swap(p[i].first, p[i].second);
if (check(x, y, p[i].first, p[i].second)) {
flip(x, y, p[i].first, p[i].second);
self(self);
flip(x, y, p[i].first, p[i].second);
}
swap(p[i].first, p[i].second);
bit ^= (1 << i);
}
};
dfs(dfs);
cout << flag << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
1 1 1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3516kb
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: 0ms
memory: 3596kb
input:
5 3 5 5 3 3 3 5
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
1 2 4 8 16 32 64 128
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
4 4 2 1 4 4 2 1
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 5ms
memory: 3672kb
input:
995 51 559 565 154 536 56 780
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 14ms
memory: 3704kb
input:
391 694 540 42 240 937 691 246
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 47ms
memory: 3656kb
input:
519 411 782 710 299 45 21 397
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 6ms
memory: 3580kb
input:
96 960 948 18 108 82 371 576
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
3 2 4 3 3 1 1 4
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 3 1 2 4 4 3 2
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4 4 1 3 5 4 2 5
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 96ms
memory: 4076kb
input:
1000 1000 1000 1000 1000 1000 1000 1000
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 83ms
memory: 4192kb
input:
1000 999 998 1000 997 1000 997 997
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 3 3 3 3 3 4 7
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 5 5 4 7 1 6 2
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
12 2 12 7 7 12 16 4
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
7 2 2 14 5 14 7 12
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
32 36 5 1 1 37 35 5
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
28 30 30 1 31 1 2 30
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
66 68 9 11 7 66 9 64
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
59 44 25 44 40 32 40 52
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
4 4 2 3 4 2 3 2
output:
1
result:
ok single line: '1'