QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#524956#5460. Sum of Numberssolar_express#WA 282ms3876kbC++232.1kb2024-08-20 10:54:242024-08-20 10:54:24

Judging History

你现在查看的是最新测评结果

  • [2024-08-20 10:54:24]
  • 评测
  • 测评结果:WA
  • 用时:282ms
  • 内存:3876kb
  • [2024-08-20 10:54:24]
  • 提交

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 == 4) {
    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-1<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-1;
    dfs(i+1,len+j, s+j*(base+i-1));
  }
}

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';
      lenans = n;
      reverse(s, s+n);
      base = n/k;
      memcpy(ans, s, n);
      // 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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3876kb

input:

2
8 1
45455151
2 1
42

output:

9696
6

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 282ms
memory: 3792kb

input:

10
1301 6
56328399613959594774559774218276494124991536454496431869449134772679831477279356599352619469813771742358572734317965823527349354276551857226632977613336815474383422853946661428822284645652423563864641261338984158269966469425994769486371736593879954275146732544891889693921182364554588732946...

output:

40171474642642313379012206249814531518482788641676883444432619360834637502289764871075555753328074747567851504303869046042417321062348027566219131193668402077719822877038895666962428717
532273349418403140060871185857451731387676700003713359284145061073761198421735413320898470225931591475648547225370...

result:

wrong answer 1st lines differ - expected: '286183755510664079479706773787...6909797866802717925250679901255', found: '401714746426423133790122062498...2077719822877038895666962428717'