QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714668 | #5460. Sum of Numbers | qtoq | WA | 40ms | 6184kb | C++17 | 3.4kb | 2024-11-06 02:03:21 | 2024-11-06 02:03:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef ONPC
#define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define deb(...)
#endif
// c++ short types
#define vt vector
//typedef long long ll;
typedef long double ld;
void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
// const int mod = 1e9 + 7;
const int mod = 998244353;
const int inf = 1e9;
const int64_t infll = 1e13;
bool debug = false;
const ld eps = 1e-9;
const ld pi = acos(-1);
mt19937_64 rng((int) chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5, K = 10;
int subvalue[maxn][K];
struct num {
const int base = 1000'000'000;
vt<int> elems;
num(int x = 0) {
elems = {x};
}
num(int l, int r) {
for(int i = l; i <= r; i += 9) {
elems.push_back(subvalue[i][min(9, r-i+1)]);
}
if(elems.empty()) {
elems = {0};
}
}
void add(num &b) {
int carry = 0;
for(int i = 0; i < max(elems.size(), b.elems.size()) || carry > 0; ++i) {
if(elems.size() == i) {
elems.push_back(0);
}
elems[i] += carry + (i < b.elems.size() ? b.elems[i] : 0);
carry = elems[i] >= base;
if(carry) {
elems[i] -= base;
}
}
}
void print() {
while(not elems.size() > 1 and elems.back() == 0) {
elems.pop_back();
}
if(elems.empty()) {
elems.push_back(0);
}
for(int i = elems.size() - 1; i >= 0; --i) {
cout << elems[i];
}
cout << '\n';
}
};
bool cmp(num &a, num &b) {
if(a.elems.size() != b.elems.size()) {
return a.elems.size() < b.elems.size();
}
for(int i = a.elems.size()-1; i>=0; --i) {
if(a.elems[i] != b.elems[i]){
return a.elems[i] < b.elems[i];
}
}
return true;
}
void solve() {
int n, k;
cin >> n >> k;
string s; cin >> s;
for(int i = 0; i < n; ++i) {
for(int j = 1; j < K; ++j) {
subvalue[i][j] = stoi(s.substr(i, j));
}
}
int z = n / (k+1);
num res(0, s.size()-1);
auto Dfs = [&](auto self, int id, int sum, num val = 0) -> void {
if(sum + (k-id+1)*(z-1) > n || sum + (k-id+1)*(z+1) < n) {
return ;
}
if(!cmp(val, res)) {
return ;
}
if(sum >= n || id == k + 1) {
if(id == k + 1 and sum == n) {
swap(res.elems, val.elems);
}
return ;
}
for(auto y: {z-1, z, z+1}) if(y > 0) {
num tmp = val, addend = {sum, sum + y - 1};
tmp.add(addend);
self(self, id + 1, sum + y, tmp);
}
};
Dfs(Dfs, 0, 0);
res.print();
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int tt = 1;;
if(debug) {
tt = 1e3;
} else {
cin >> tt;
}
for(int t = 0; t < tt; ++t) {
solve();
}
#ifdef ONPC
whattime();
#endif
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
2 8 1 45455151 2 1 42
output:
9696 6
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 40ms
memory: 6184kb
input:
10 1301 6 56328399613959594774559774218276494124991536454496431869449134772679831477279356599352619469813771742358572734317965823527349354276551857226632977613336815474383422853946661428822284645652423563864641261338984158269966469425994769486371736593879954275146732544891889693921182364554588732946...
output:
3133134925250679866802719196909798377930722423508575800651748225191735990933507603809414526439565034352629356630727749578287350939159587940686764065879913860797067738106640794761837551 1257315146561308627813869366354897220604851013844287825194156529733440079645117121292160449344404306829731802716046...
result:
wrong answer 1st lines differ - expected: '286183755510664079479706773787...6909797866802717925250679901255', found: '313313492525067986680271919690...3860797067738106640794761837551'