ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#377 | #50. 「NOIP2012」国王游戏 | Pigsyy | 100 | 444ms | 7960kb | C++23 | 6.5kb | 2025-04-22 21:04:22 | 2025-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"