QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#707344#6563. Four Squaretassei903#AC ✓96ms4192kbC++234.0kb2024-11-03 15:35:082024-11-03 15:35:08

Judging History

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

  • [2024-11-03 15:35:08]
  • 评测
  • 测评结果:AC
  • 用时:96ms
  • 内存:4192kb
  • [2024-11-03 15:35:08]
  • 提交

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'