QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#855767 | #885. Keep Calm And Carry Off | FUCKUCUP | WA | 343ms | 23384kb | C++20 | 2.0kb | 2025-01-13 10:33:36 | 2025-01-13 10:33:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
string s, t;
int n, a[maxn], b[maxn], f[maxn];
inline void init(string &s) {
reverse(s.begin(), s.end());
for(int i = n - s.length() + 1; i; --i) s += '0';
reverse(s.begin(), s.end());
}
inline string init2(string s) {
reverse(s.begin(), s.end());
while(s.back() == '0') s.pop_back();
reverse(s.begin(), s.end());
if(s.empty()) s = "0";
return s;
}
inline string solve(const string &s, const string &t) {
memset(a, 0, sizeof a), memset(b, 0, sizeof b);
int l = 0, r = n;
string ans;
while(l <= r) {
int md = l + r >> 1;
string res;
for(int i = n; i >= 0; --i) a[n - i] = s[i] - '0';
for(int i = n; i >= 0; --i) b[n - i] = t[i] - '0';
for(int i = 0; i < md; ++i) {
if(a[i] > 9) a[i] = 0, ++a[i + 1];
if(b[i] < 0) b[i] = 9, --b[i + 1];
if(a[i]) {
int d = 10 - a[i];
if(b[i] >= d) b[i] -= d;
else b[i] = b[i] + 10 - d, --b[i + 1];
a[i] = 0, ++a[i + 1], res += d + '0';
}else res += '0';
}
for(int i = md; i <= n; ++i) {
if(a[i] > 9) a[i] = 0, ++a[i + 1];
if(b[i] < 0) b[i] = 9, --b[i + 1];
}
// cout << "---\n";
// for(int i = 0; i <= n; ++i) cout << a[i]; cout << '\n';
// for(int i = 0; i <= n; ++i) cout << b[i]; cout << '\n';
reverse(res.begin(), res.end());
bool flag = true;
for(int i = 0; i <= n; ++i) if(a[i] + b[i] > 9) flag = false;
if(flag && b[n + 1] == 0) ans = res, r = md - 1;
else l = md + 1, b[n + 1] = 0;
// cout << md << ' ' << res << ' ' << flag << '\n';
}
// cout << "ans = " << ans << ' ' << ans.length() << ' ' << n << '\n';
init(ans);
return ans;
}
inline void solve() {
cin >> s >> t, n = max(s.length(), t.length());
init(s), init(t);
string ans1 = solve(s, t), ans2 = solve(t, s);
cout << init2(min({s, t, ans1, ans2})) << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 12168kb
input:
10 99
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 13520kb
input:
90 10
output:
10
result:
ok answer is '10'
Test #3:
score: 0
Accepted
time: 3ms
memory: 13392kb
input:
23425 487915
output:
12085
result:
ok answer is '12085'
Test #4:
score: 0
Accepted
time: 0ms
memory: 12688kb
input:
1 1
output:
0
result:
ok answer is '0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 12576kb
input:
99 99
output:
1
result:
ok answer is '1'
Test #6:
score: 0
Accepted
time: 2ms
memory: 11992kb
input:
14 86
output:
14
result:
ok answer is '14'
Test #7:
score: 0
Accepted
time: 2ms
memory: 11700kb
input:
899999999999999999999 100000000000000000001
output:
100000000000000000001
result:
ok answer is '100000000000000000001'
Test #8:
score: 0
Accepted
time: 224ms
memory: 20312kb
input:
615357649595284099508435993883986571313695656691562389866620971630644953030429613681442060702023197532680463771166724257258948140032009435767225187778914625685600736964207275868974321513156027752788270804733647164380664571327109020774746630643814103150883559720458844636326901760106285413007100737536...
output:
226164757855375706179130034126837577710545348626568907238536520434546544085882446273981029021778063112888523241983297218947698252532826120194967039881313867888258883810876610793168815193851023510269144054457285631520878535365581681349042349672439715344120755176307571379581412256786498122023796566813...
result:
ok answer is '226164757855375706179130034126...1032113015742081980588406310856'
Test #9:
score: 0
Accepted
time: 110ms
memory: 21556kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok answer is '0'
Test #10:
score: 0
Accepted
time: 227ms
memory: 22540kb
input:
946678535444896475642225008527348253117127344137446723931302495407581979054231432196768653557235697280697999349345542859864503525832718970888297969471590384454809084105146882526427617822167077225221683317423530502375438306992125794196668936915418103664819269986191955766257534524689071638219238188976...
output:
533214645551035243577749914726517468828726558625532760686975045924180209457685678032313464427643027193020006506544571401354964741672810291117020305284096155451909158948531174735723821778329227747783166825764694976245616930078742058033310630845818963351807300138080442337424654753109283617807618110239...
result:
ok answer is '533214645551035243577749914726...8583282299712982139175537021362'
Test #11:
score: 0
Accepted
time: 207ms
memory: 21760kb
input:
794946477760061325408107597512810946289384941381736255316518687888511341258007534679058032849319730631613743099733353038802970355718221088259886925518970281655634779851495550264110452025361079238655051609110357880450805087197804035613307707314768911650131971835865731706270390379379832722335057330470...
output:
205053522239938674591892402487189053710615058618263744683481312111488658741992465320941967150680269368386256900266646961197029644281778911740113074481029718344365220148504449735889547974638920761344948390889642119549194912802195964386692292685231088349868028164134268293729609620620167277664942669529...
result:
ok answer is '205053522239938674591892402487...4895693158694032335924691582580'
Test #12:
score: 0
Accepted
time: 209ms
memory: 22840kb
input:
740396512715746854480688476727726843695909844190398984187893683516689175082139997856915168192558523514785642438089549764358594098561796813209038321522889191781035343854374929109665898552729746770608711636305055090924461862639090335815510632703670463147194228154033606862279586041022594067305712355803...
output:
259603487284253145519311523272273156304090155809601015812106316483310824917860002143084831807441476485214357561910450235641405901438203186790961678477110808218964656145625070890334101447270253229391288363694944909075538137360909664184489367296329536852805771845966393137720413958977405932694287644196...
result:
ok answer is '259603487284253145519311523272...7124298880143408010404228204895'
Test #13:
score: 0
Accepted
time: 180ms
memory: 23384kb
input:
808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080...
output:
191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919...
result:
ok answer is '191919191919191919191919191919...9191919191919191919191919191920'
Test #14:
score: 0
Accepted
time: 112ms
memory: 20012kb
input:
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 185ms
memory: 21848kb
input:
888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok answer is '111111111111111111111111111111...1111111111111111111111111111112'
Test #16:
score: 0
Accepted
time: 179ms
memory: 22376kb
input:
499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
result:
ok answer is '499999999999999999999999999999...9999999999999999999999999999999'
Test #17:
score: -100
Wrong Answer
time: 343ms
memory: 22188kb
input:
902851346436306806616375942396607826120232155242259147614243592903405735290837981154314613604373937058180635157768204138128396693345023355887820571704408856138693881765209464570723015717187118417699724996521322468835282812828545349457610944807873712140962669646920063042802116551616341958682221180684...
output:
0
result:
wrong answer expected '739784808063119079929960519131...1948627624188898000206620879303', found '0'