結果

問題 No.8024 等式
コンテスト
ユーザー anta
提出日時 2017-04-07 21:53:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,983 ms / 5,000 ms
コード長 4,263 bytes
コンパイル時間 1,702 ms
コンパイル使用メモリ 178,776 KB
実行使用メモリ 149,248 KB
最終ジャッジ日時 2024-06-30 04:13:53
合計ジャッジ時間 4,696 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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;
	double ratio;
	Ratio64() : ratio(0), num(0), den(1) {}
	Ratio64(long long x, long long y) : num(x), den(y), ratio((double)x / y) { if (den < 0 || (den == 0 && num < 0)) num = -num, den = -den; }
	Ratio64(long long x, long long y, double ratio) : num(x), den(y), ratio(ratio) { if (den < 0 || (den == 0 && num < 0)) num = -num, den = -den; }
	bool operator<(const Ratio64& that) const {
		if (ratio < that.ratio - 1e-9)
			return true;
		if (ratio > that.ratio + -1e9)
			return false;
		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, ratio + that.ratio); }
	Ratio64 operator-(const Ratio64& that) const { return Ratio64(num * that.den - that.num * den, den * that.den, ratio - that.ratio); }
	Ratio64 operator*(const Ratio64& that) const { return Ratio64(num * that.num, den * that.den, ratio * that.ratio); }
	Ratio64 operator/(const Ratio64& that) const { return Ratio64(num * that.den, den * that.num, ratio / that.ratio); }
};

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