QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56661#3889. Balanced Breakdownt3alaMsMs#WA 156ms3696kbC++233.0kb2022-10-20 23:24:232022-10-20 23:24:26

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-20 23:24:26]
  • Judged
  • Verdict: WA
  • Time: 156ms
  • Memory: 3696kb
  • [2022-10-20 23:24:23]
  • Submitted

answer

/// MANGA
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;

#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace __gnu_pbds;
using namespace __gnu_cxx;

using ll = long long;
using ii = pair<int, int>;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define pb push_back
#define F first
#define S second
#define f(i, a, b)  for(int i = a; i < b; i++)
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define mp make_pair
#define popCnt(x) (__builtin_popcountll(x))

const int N = 4e5+5, LG = log2(N) + 1, MOD = 998244353;
const double PI = acos(-1);
string s;
vector<string> ans;
string rev(string s){
    reverse(all(s));
    return s;
}
string nadaf(string s) {
    for(int i = 0; i < s.size(); i++)
    if(s[i] != '0') {
        return s.substr(i);
    }
    return "0";
}
string sub(string s, string y) {
    if(y == "1") {
        for(int i = s.size()-1; i >= 0; --i) {
            if(s[i] >= '1') {
                s[i] -= 1;
                for(int j = i + 1; j < s.size(); j++)s[j] = '9';
                return nadaf(s);
            }
        }
    }
    while(sz(y) < sz(s))y = "0" + y;
    int carry = 0;
    for(int i = s.size() - 1; i >= 0; --i) {
        int val1 = s[i] - '0';
        int val2 = y[i] - '0';
        if(val1-carry >= val2) {
            val1 =  val1 - carry - val2;
            carry = 0;
        }   else {
            val1 = val1 + 10 - carry - val2;
            carry = 1;
        }
        s[i] = val1 + '0';
    }
    return nadaf(s);
}
void solve(string s) {
    if(s.size() == 1) {
        if(s!="0")
        ans.push_back(s);
        return;
    }
    if(s=="10") {
        ans.push_back("5");
        ans.push_back("5");
        return;
    }
    if(s=="100") {
        ans.pb("55");
        ans.pb("44");
        ans.pb("1");
        return;
    }
    if(s.size() == 2) {
        if(s[1] >= s[0]) {
            ans.pb(string(1,s[0])+string(1,s[0]));
        }   else {
            ans.pb(string(1,s[0]-1)+string(1,s[0]-1));
        }
        solve(sub(s,ans.back()));
        return;
    }
    string x = s.substr(0,s.size()/2);
    if(s.size() & 1) {
        if(x+"0"+rev(x) > s) x = sub(x,"1");
        ans.pb(x+"0"+rev(x));
    }   else {
        if(x+rev(x)>s)x = sub(x,"1");
        ans.pb(x+rev(x));
    }
    solve(sub(s,ans.back()));
}
void doWork() {
    string s;
    cin >> s;
    ans.clear();
    solve(s);
    cout << ans.size() << '\n';
    for(auto x : ans)cout << x << "\n";
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE
    int t = 1;
    cin >> t;
    while (t--) {
        doWork();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 156ms
memory: 3696kb

input:

1100000

output:

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

...

result:

FAIL Sum of numbers is not 1100000