結果

問題 No.3024 等式
ユーザー antaanta
提出日時 2017-03-31 23:02:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4,224 ms / 5,000 ms
コード長 3,896 bytes
コンパイル時間 1,724 ms
コンパイル使用メモリ 176,852 KB
実行使用メモリ 149,632 KB
最終ジャッジ日時 2024-06-30 04:13:44
合計ジャッジ時間 7,932 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 4 ms
6,944 KB
testcase_07 AC 4 ms
6,944 KB
testcase_08 AC 4 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 4 ms
6,940 KB
testcase_12 AC 66 ms
8,064 KB
testcase_13 AC 70 ms
7,936 KB
testcase_14 AC 97 ms
9,984 KB
testcase_15 AC 20 ms
6,940 KB
testcase_16 AC 4 ms
6,940 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 498 ms
21,888 KB
testcase_19 AC 495 ms
22,656 KB
testcase_20 AC 5 ms
6,940 KB
testcase_21 AC 4 ms
6,944 KB
testcase_22 AC 4,224 ms
149,632 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

void umul64x64(uint64_t x, uint64_t y, uint64_t *hi, uint64_t *lo) {
	uint32_t xlo = (uint32_t)x, xhi = (uint32_t)(x >> 32);
	uint32_t ylo = (uint32_t)y, yhi = (uint32_t)(y >> 32);
	uint64_t xyll = (uint64_t)xlo * ylo;
	uint64_t xylh = (uint64_t)xlo * yhi;
	uint64_t xyhl = (uint64_t)xhi * ylo;
	uint64_t xyhh = (uint64_t)xhi * yhi;
	uint32_t m0 = (uint32_t)(xyll >> 32);
	uint32_t m1 = (uint32_t)xylh;
	uint32_t m2 = (uint32_t)xyhl;
	uint64_t m = (uint64_t)m0 + m1 + m2;
	*lo = (uint32_t)xyll | (m << 32);
	*hi = (m >> 32) + (xylh >> 32) + (xyhl >> 32) + xyhh;
}

int compareRatioUnsigned(uint64_t a, uint64_t b, uint64_t c, uint64_t d) {
	uint64_t xhi, yhi;
	uint64_t xlo, ylo;
	umul64x64(a, d, &xhi, &xlo);
	umul64x64(c, b, &yhi, &ylo);
	if (xhi != yhi)
		return xhi > yhi ? 1 : -1;
	else if (xlo != ylo)
		return xlo > ylo ? 1 : -1;
	else
		return 0;
}

int compareRatio(long long a, long long b, long long c, long long d) {
	assert(b >= 0 && d >= 0);
	if (a == 0 || d == 0)
		return c == 0 || b == 0 ? 0 : c > 0 ? -1 : 1;
	else if (c == 0 || b == 0)
		return a > 0 ? 1 : -1;

	if (a < 0) {
		if (c < 0)
			return -compareRatioUnsigned((uint64_t)-a, b, (uint64_t)-c, d);
		else
			return -1;
	} else {
		if (c < 0)
			return 1;
		else
			return compareRatioUnsigned((uint64_t)a, b, (uint64_t)c, d);
	}
}

struct Ratio64 {
	long long num, den;
	Ratio64() : num(0), den(1) {}
	Ratio64(long long x, long long y) : num(x), den(y) { if (den < 0 || (den == 0 && num < 0)) num = -num, den = -den; }
	bool operator<(const Ratio64& that) const {
		return compareRatio(num, den, that.num, that.den) < 0;
	}
	double toDouble() const {
		return (double)num / den;
	}
	Ratio64 operator+(const Ratio64& that) const { return Ratio64(num * that.den + that.num * den, den * that.den); }
	Ratio64 operator-(const Ratio64& that) const { return Ratio64(num * that.den - that.num * den, den * that.den); }
	Ratio64 operator*(const Ratio64& that) const { return Ratio64(num * that.num, den * that.den); }
	Ratio64 operator/(const Ratio64& that) const { return Ratio64(num * that.den, den * that.num); }
};

int main() {
	int n;
	while (~scanf("%d", &n)) {
		vector<int> A(n);
		for (int i = 0; i < n; ++ i)
			scanf("%d", &A[i]);
		vector<set<Ratio64>> dp(1 << n);
		bool ans = false;
		reu(mask, 1, 1 << n) {
			for (int subs = (mask - 1) & mask; subs > 0; (-- subs) &= mask) {
				const auto &X = dp[subs], &Y = dp[mask - subs];
				for (const auto &x : X) {
					ans |= Y.count(x) != 0;
				}
			}
			if (ans)
				break;
			if (mask + 1 == (1 << n))
				break;

			auto &S = dp[mask];
			if ((mask & (mask - 1)) == 0) {
				rep(i, n) if(mask >> i & 1)
					S.insert(Ratio64(A[i], 1));
			} else {
				for (int subs = (mask - 1) & mask; subs > 0; (-- subs) &= mask) {
					const auto &X = dp[subs], &Y = dp[mask - subs];
					for (const auto &x : X) for (const auto &y : Y) {
						S.insert(x + y);
						if(!(x < y))
							S.insert(x - y);
						S.insert(x * y);
						if(y.num != 0)
							S.insert(x / y);
					}
				}
			}
			/*
			cerr << mask << ": " << S.size() << endl;
			if (mask + 1 == (1 << n)) {
				rep(i, n) if (mask >> i & 1)
					cerr << A[i] << " ";
				cerr << ": ";
				for (auto x : S)
					cerr << x.num << "/" << x.den << " ";
				cerr << endl;
			}
			*/
		}
		puts(ans ? "YES" : "NO");
	}
	return 0;
}
0