QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#855767#885. Keep Calm And Carry OffFUCKUCUPWA 343ms23384kbC++202.0kb2025-01-13 10:33:362025-01-13 10:33:38

Judging History

This is the latest submission verdict.

  • [2025-01-13 10:33:38]
  • Judged
  • Verdict: WA
  • Time: 343ms
  • Memory: 23384kb
  • [2025-01-13 10:33:36]
  • Submitted

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'