QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#524935 | #5460. Sum of Numbers | solar_express# | WA | 852ms | 3760kb | C++23 | 2.1kb | 2024-08-20 10:39:36 | 2024-08-20 10:39:36 |
Judging History
answer
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
const int N = 3e5+5, M = 2e6;
int n, k, base;
char s[N];
char res[N];
char ans[N];
int lenans;
void update_ans(vector<int> len) {
sort(begin(len), end(len));
int ul = *len.rbegin();
do {
vector<int> p(k);
for (int i = 1; i < k; ++i) p[i] += len[i-1];
char carry = 0;
int lenres = 0;
for (int i = 0; i < ul; ++i) {
char cur = carry;
for (int j = 0; j < k; ++j) if (i < len[j]) {
cur += s[p[j]+i];
}
res[i] = cur % 10;
carry = cur / 10;
++lenres;
}
if (carry) res[lenres++] = carry;
bool upd = 0;
if (lenres < lenans) upd = 1;
else if (lenres == lenans) {
for (int i = lenres - 1; i >= 0; --i) {
if (res[i] < ans[i]) {
upd = 1;
break;
}
}
}
if (upd) {
for (int i = 0; i < lenres; ++i) ans[i] = res[i];
lenans = lenres;
}
} while (next_permutation(begin(len), end(len)));
}
int val[10];
void dfs(int i, int len, int s) {
if (i == 5) {
if (len == k && s == n) {
vector<int> p;
for (int j = 0; j < k; ++j) p.push_back(val[j]);
update_ans(p);
}
return;
}
if (base+i-2<1) return dfs(i+1,len,s);
if (len > k || s > n) return;
for (int j = 0; j <= k; ++j) {
for (int l = 0; l < j; ++l) val[len+l] = base+i-2;
dfs(i+1,len+j, s+j*(base+i-2));
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
cin >> n >> k >> s;
k = min(k+1, n);
for (int i = 0; i < n; ++i) s[i] -= '0';
memcpy(ans, s, n);
lenans = n;
reverse(s, s+n);
base = n/k;
// vector<int> len(k, n/k);
// for (int i = 0; i < n%k; ++i) len[k-i-1]+=1;
// update_ans(len);
dfs(0,0,0);
for (int i = lenans-1; i >= 0; --i) {
cout << char(ans[i]+'0');
}
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
2 8 1 45455151 2 1 42
output:
9696 6
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 852ms
memory: 3760kb
input:
10 1301 6 56328399613959594774559774218276494124991536454496431869449134772679831477279356599352619469813771742358572734317965823527349354276551857226632977613336815474383422853946661428822284645652423563864641261338984158269966469425994769486371736593879954275146732544891889693921182364554588732946...
output:
0171474642642313379012206249814531518482788641676883444432619360834637502289764871075555753328074747567851504303869046042417321062348027566219131193668402077719822877038895666962428717 3410561168937637661946628326178332526754855382338700330116128071138181448874450807324275490482036922277234026649694...
result:
wrong answer 1st lines differ - expected: '286183755510664079479706773787...6909797866802717925250679901255', found: '017147464264231337901220624981...2077719822877038895666962428717'