QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56661 | #3889. Balanced Breakdown | t3alaMsMs# | WA | 156ms | 3696kb | C++23 | 3.0kb | 2022-10-20 23:24:23 | 2022-10-20 23:24:26 |
Judging History
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