Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377#50. 「NOIP2012」国王游戏Pigsyy100444ms7960kbC++236.5kb2025-04-22 21:04:222025-04-22 21:04:23

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int base = 1e8;
int ta[1000005], tb[1000005], tc[1000005];
struct BigInt {
	std::vector<int> num;
	int sym;
	BigInt() {
		sym = 0;
	}
	void read() {
		string s;
		cin >> s;
		if (s[0] == '-') sym = 1, s.erase(0, 1);
		reverse(s.begin(), s.end());
		int tmp = 0, has = 0;
		for (auto v : s) {
			tmp = tmp + (v ^ 48) * pow(10, has), has ++;
			if (has == 8) {
				num.emplace_back(tmp);
				tmp = 0, has = 0;
			}
		}
		if (tmp) num.emplace_back(tmp);
		reverse(num.begin(), num.end());
	}
	void print() {
		if (sym == 1) cout << '-';
		for (int i = 0; i < num.size(); i ++)
			if (i != 0)
				printf("%08lld", num[i]);
			else
				printf("%lld", num[i]);
	}
	int operator< (BigInt const &tmp)const {
		if (num.size() < tmp.num.size()) return 1;
		else if (num.size() > tmp.num.size()) return 0;
		else {
			for (int i = 0; i < num.size(); i ++)
				if (tmp.num[i] == num[i]) continue;
				else {
					if (tmp.num[i] > num[i]) return 1;
					else return 0;
				}
			return 2;
		}
	}
	int to_int() {
		int n = num.size(), sum = 0;
		for (int i = 0; i < n; i ++)
			sum = sum * base + num[i];
		return sum;
	}
};

BigInt maxb(BigInt a, BigInt b) {
	if (a < b) return b;
	else return a;
}
BigInt to_big(int x) {
	BigInt res;
	while (x) {
		res.num.emplace_back(x % base);
		x /= base;
	}
	return res;
}
void Fill(vector<int> &ta, int x) {
	vector<int> res;
	int rest = x - (int)ta.size();
	for (int i = 1; i <= rest; i ++)
		res.emplace_back(0);
	for (auto i : ta)
		res.emplace_back(i);
	ta = res;
}
void Del(BigInt &tmp) {
	BigInt res;
	int flg = 0;
	for (int i = 0; i < tmp.num.size(); i ++)
		if (flg || tmp.num[i]) flg = 1, res.num.emplace_back(tmp.num[i]);
	if (!res.num.size()) res.num.emplace_back(0);
	tmp = res;
}
BigInt sum(BigInt tmp1, BigInt tmp2) {
	std::vector<int> ta = tmp1.num, tb = tmp2.num;
	if (ta.size() > tb.size()) swap(ta, tb);
	Fill(ta, (int)tb.size());
	int n = ta.size(), jw = 0;
	BigInt res;
	for (int i = n - 1; i >= 0; i --) {
		int tmp = ta[i] + tb[i] + jw;
		res.num.emplace_back(tmp % base);
		jw = tmp / base;
	}
	if (jw) res.num.emplace_back(jw);
	reverse(res.num.begin(), res.num.end());
	return res;
}
BigInt substract(BigInt tmp1, BigInt tmp2) {
	BigInt res;
	if ((tmp1 < tmp2) == 2 && tmp1.sym == tmp2.sym) {
		res.num.emplace_back(0);
		return res;
	}
	if (tmp1 < tmp2) swap(tmp1, tmp2), res.sym = 1;
	std::vector<int> ta = tmp1.num, tb = tmp2.num;
	Fill(tb, (int)ta.size());
	int n = ta.size(), jw = 0;
	for (int i = n - 1; i >= 0; i --) {
		jw = ta[i] - jw - tb[i];
		res.num.emplace_back((jw + base) % base);
		jw = (jw < 0);
	}

	reverse(res.num.begin(), res.num.end());
	Del(res);
	return res;
}
BigInt operator+ (BigInt tmp1, BigInt tmp2) {
	if (tmp1.sym == 0 && tmp2.sym == 0) return sum(tmp1, tmp2);
	else if (tmp1.sym == 1 && tmp2.sym == 1) {
		BigInt res = sum(tmp1, tmp2);
		res.sym = 1;
		return res;
	} else {
		if (tmp1.sym == 1) swap(tmp1, tmp2);
		BigInt res = substract(tmp1, tmp2);
		return res;
	}
}
BigInt operator- (BigInt tmp1, BigInt tmp2) {
	if (tmp1.sym == 0 && tmp2.sym == 0) {
		return substract(tmp1, tmp2);
	} else if (tmp1.sym == 1 && tmp2.sym == 1) {
		return substract(tmp2, tmp1);
	} else {
		if (tmp1.sym == 1) {
			BigInt res = sum(tmp1, tmp2);
			res.sym = 1;
			return res;
		} else {
			return sum(tmp1, tmp2);
		}
	}
}
void push_zero(BigInt &x, int cnt) {
	int m = x.num.size();
	x.num[m - 1] = x.num[m - 1] * pow(10, cnt % 8);
	for (int i = m - 1; i >= 0; i --)
		if (x.num[i] > base - 1) {
			if (i == 0) x.num.insert(x.num.begin(), x.num[i] / base);
			else x.num[i - 1] += x.num[i] / base;
			x.num[i] %= base;
		}
	for (int i = 1; i <= cnt / 8; i ++)
		x.num.emplace_back(0);
}
BigInt mul(BigInt tmp1, BigInt tmp2) {
	if (tmp1.num.size() > tmp2.num.size()) swap(tmp1, tmp2);
	Fill(tmp1.num, tmp2.num.size());
	reverse(tmp1.num.begin(), tmp1.num.end());
	reverse(tmp2.num.begin(), tmp2.num.end());
	while (tmp1.num.size() > 1 && tmp1.num.back() == 0 && tmp2.num.back() == 0) tmp1.num.pop_back(), tmp2.num.pop_back();
	reverse(tmp1.num.begin(), tmp1.num.end());
	reverse(tmp2.num.begin(), tmp2.num.end());
	if (tmp2.num.size() <= 1025) {
		BigInt res;
		int lena = tmp1.num.size(), lenb = tmp2.num.size(), flg1 = 0, flg2 = 0;
		for (int i = 1; i <= lenb + 1; i ++)
			for (int j = 1; j <= lena + 1; j ++)
				tc[i + j - 1] = 0;
		for (int i = 1; i <= lena; i ++) ta[i] = tmp1.num[lena - i];
		for (int i = 1; i <= lenb; i ++) tb[i] = tmp2.num[lenb - i];
		for (int i = 1; i <= lenb; i ++)
			for (int j = 1; j <= lena; j ++)
				tc[i + j - 1] += ta[j] * tb[i];
		for (int i = 1; i < lena + lenb; i ++)
			if(tc[i] > base - 1) {
				tc[i + 1] += tc[i] / base;
				tc[i] %= base;
			}
		int len = lena + lenb;
		while (tc[len] == 0 && len > 1) len --;
		for (int i = len; i >= 1; i --) res.num.emplace_back(tc[i]);

		return res;
	}

	int n = tmp1.num.size();
	BigInt a1, a2, b1, b2;
	for (int i = 0; i < n / 2; i ++)
		a1.num.emplace_back(tmp1.num[i]), b1.num.emplace_back(tmp2.num[i]);
	for (int i = n / 2; i < n; i ++)
		a2.num.emplace_back(tmp1.num[i]), b2.num.emplace_back(tmp2.num[i]);
	BigInt x = mul(a1, b1), y = mul(a2, b2), z = mul(a1 + a2, b1 + b2) - x - y;
	push_zero(x, (n - n / 2) * 2 * 8);
	push_zero(z, (n - n / 2) * 8);

	Del(x), Del(y), Del(z);
	BigInt tmp = x + y + z;
	return x + y + z;
}
BigInt operator* (BigInt tmp1, BigInt tmp2) {
	int s = tmp1.sym ^ tmp2.sym;
	tmp1.sym = 0, tmp2.sym = 0;
	BigInt res = mul(tmp1, tmp2);
	res.sym = s;
	return res;
}
BigInt operator/ (BigInt tmp, int x) {
	BigInt res;
	int sum = 0;
	for (auto v : tmp.num) {
		sum = sum * base + v;
		res.num.emplace_back(sum / x);
		sum %= x;
	}

	Del(res);
	return res;
}
int operator% (BigInt tmp, int x) {
	BigInt res;
	int sum = 0;
	for (auto v : tmp.num) {
		sum = sum * base + v;
		res.num.emplace_back(sum / x);
		sum %= x;
	}

	return sum;
}

const int N = 1e3 + 10;

int n, ga, gb;
PII a[N];

bool cmp(PII i, PII j) {
	return i.first * i.second < j.first * j.second;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> ga >> gb;
	for (int i = 1; i <= n; i ++)
		cin >> a[i].first >> a[i].second;

	sort(a + 1, a + 1 + n, cmp);

	BigInt res, tmp = to_big(ga);
	for (int i = 1; i <= n; i ++)
		res = maxb(res, tmp / a[i].second), tmp = tmp * to_big(a[i].first);

	res.print();

	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 2ms
memory: 7656kb

input:

3
1 7
6 1
2 3
2 3

output:

4

result:

ok "4"

Test #2:

score: 10
Accepted
time: 2ms
memory: 7724kb

input:

10
5 7
4 2
7 3
7 2
4 4
1 7
5 3
6 1
4 5
2 3
3 7

output:

134400

result:

ok "134400"

Test #3:

score: 10
Accepted
time: 1ms
memory: 7776kb

input:

15
7 2
1 6
4 5
5 1
1 6
4 1
5 3
5 2
2 4
4 3
5 5
7 4
4 5
1 3
5 4
6 6

output:

13066666

result:

ok "13066666"

Test #4:

score: 10
Accepted
time: 3ms
memory: 7460kb

input:

20
1 5
2 4
2 5
6 4
3 2
1 2
6 6
1 2
7 7
6 7
6 3
5 6
1 4
2 4
1 3
7 3
7 2
3 3
6 6
1 2
3 5

output:

58786560

result:

ok "58786560"

Test #5:

score: 10
Accepted
time: 0ms
memory: 7520kb

input:

100
70 94
43 9
92 18
18 9
86 31
24 32
46 49
23 69
40 56
27 75
28 85
37 29
99 80
44 70
14 9
30 38
46 ...

output:

2166489661101032350678866897536628698296804147316726878162441737980268621335310233327258927458239967...

result:

ok "216648966110103235067886689753...3620140885606400000000000000000"

Test #6:

score: 10
Accepted
time: 3ms
memory: 7728kb

input:

100
1 1
1 1
2 1
2 2
1 2
1 2
2 2
1 2
1 2
2 2
2 2
1 2
2 1
1 2
1 2
1 2
1 2
2 2
1 2
1 1
1 1
1 1
1 1
1 2
...

output:

268435456

result:

ok "268435456"

Test #7:

score: 10
Accepted
time: 54ms
memory: 7864kb

input:

1000
6 52
100 69
7 1
72 90
39 63
73 2
23 32
53 100
14 52
18 56
59 47
9 73
26 68
56 16
39 7
58 38
88 ...

output:

3222336023148094993156610082101741639219638933771889556794950121285293839260791107918265919250467388...

result:

ok "322233602314809499315661008210...0000000000000000000000000000000"

Test #8:

score: 10
Accepted
time: 190ms
memory: 7688kb

input:

1000
8450 2178
9357 9872
2393 5670
2035 788
8101 2109
728 8409
7118 1068
3893 6529
9557 7797
4769 90...

output:

4028396466890621399617777001922084145816723424434458760371820414699378225122228464276211665221059309...

result:

ok "402839646689062139961777700192...2544570502431118314424635332252"

Test #9:

score: 10
Accepted
time: 186ms
memory: 7960kb

input:

1000
9211 6189
3297 589
9975 8466
80 341
779 1883
8314 39
60 7691
9107 6172
4178 8589
9747 865
5064 ...

output:

9963742014417443762100810524646454496417678234906899643076204836030037289972835352745882396926032973...

result:

ok "996374201441744376210081052464...5643200163482170225809747624399"

Test #10:

score: 10
Accepted
time: 3ms
memory: 7404kb

input:

1000
1 395
1 154
1 220
1 293
1 374
1 274
1 383
1 925
1 424
1 950
1 910
1 588
1 930
1 418
1 489
1 59
...

output:

1

result:

ok "1"