QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117722#6563. Four Squarecada_dia_mas_insanos#AC ✓1ms3476kbC++173.0kb2023-07-02 00:29:342023-07-02 00:29:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 00:29:36]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3476kb
  • [2023-07-02 00:29:34]
  • 提交

answer

// Too many mind, no mind.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <iomanip>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define COMP(x) sort(ALL(x)); x.resize(unique(ALL(x)) - (x).begin())
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)

using pii = pair <int, int>;
using vi = vector <int>;
using vpi = vector <pii>;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using ld = long double;
using vld = vector<ld>;
using vpl = vector<pll>;


bool solve(vpl a, int n, int m) {
	if (a.empty()) return m==0;
	bool ok = 0;
	int k = a.size();
	if (k >= 1) {
		forn(i, k) {
			if (a[i].fi==n) {
				vpl b;
				forn(j, k) if (i !=j) b.pb(a[j]);
				ok |= solve(b, n, m-a[i].se);
			}
		}
	} 
	if (k >= 2) {
		forn(i, k) fore(j, i+1, k-1) {
			if (a[i].fi + a[j].fi != n) continue;
			if (a[i].se == a[j].se) {
				vpl b;
				forn(l, k) if (l != i && l != j) b.pb(a[l]);
				ok |= solve(b, n, m-a[i].se);
			} else {
				int in=0;
				forn(l, k) if (l!=i && l!=j) {
					if (a[l].se == m-a[i].se && a[l].fi == a[i].fi) in++;
					else if (a[l].se == m-a[j].se && a[l].fi == a[j].fi) in++;
				}
				if (a[i].se == m || a[j].se == m) ok |= in == 1;
				else ok |= in==2;
			}
		}
	}
	if (k>=3) {
		forn(i, k) fore(j, i+1, k-1) fore(l, j+1, k-1) {
			if (a[i].fi + a[j].fi + a[l].fi == n && a[i].se == a[j].se && a[j].se == a[l].se) {
				vpl b;
				forn(it, k) if (it!=i && it!=j && it!=l) b.pb(a[it]);
				ok |= solve(b, n, m - a[i].se);
			}
		}
	}
	if (k>=4) {
		int h = 0;
		bool cur = 1;
		forn(i, k) {
			h += a[i].fi;
			cur &= a[i].se == m;
		}
		cur &= h == n;
		ok |= cur;
	}
	return ok;
}
ll root(ll n) {
	ll lo = 0, hi = n;
	while (lo < hi) {
		ll mid = lo + (hi-lo)/2;
		if (mid*mid >= n) hi=mid;
		else lo = mid+1;
	}
	return lo;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ll total = 0;
	vpl a(4);
	forn(i, 4) {
		ll h, w; cin >> h >> w;
		a[i] = mp(h, w);
		total += h*w;
	}
	sort(ALL(a));
	ll n = root(total);
	if (n*n != total) {
		cout << 0 << endl;
		return 0;
	}
	bool ok = 0;
	vi p = {0, 1, 2, 3};
	do {
		forn(mask, 16) {
			vpl b;
			forn(i, 4) b.pb(a[p[i]]);
			forn(i, 4) if (mask>>i&1) swap(b[i].fi, b[i].se);
			ok |= solve(b, n, n);
		}
	} while (next_permutation(ALL(p)));
	cout << ok << endl;
	return 0;
}

详细

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'