QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142429 | #5460. Sum of Numbers | ElDiablo# | TL | 1ms | 3524kb | C++23 | 5.6kb | 2023-08-19 04:43:38 | 2023-08-19 04:43:42 |
Judging History
answer
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T rand(T a, T b){
return uniform_int_distribution<T>(a, b)(rng);
}
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
//#define int long long
const ll mod = 998244353;
const ll INF = 1e18;
/* ----------------------------------------------------- GO DOWN ---------------------------------------------------------------------- */
bool comp (int dig1[], int dig2[], int len) {
for (int i = len - 1; i >= 0; i--) {
if (dig1[i] < dig2[i]) return false;
if (dig1[i] > dig2[i]) return true;
}
return false;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
k++;
string s;
cin >> s;
int len = (n + k - 1) / k + 40;
int dig1[len];
for (int i = 0; i < len; i++) dig1[i] = 9;
int y = n / k;
int tot = 1;
for (int i = 0; i < k; i++) tot *= 8;
for (int mask = 0; mask < tot; mask++) {
int del = 0;
int mk = mask;
bool neg2 = 0;
bool neg1 = 0;
bool neg3 = 0;
bool neg4 = 0;
bool neg5 = 0;
bool neg6 = 0;
for (int j = 0; j < k; j++) {
del += (mk % 8) - 5;
if (mk % 8 == 0) neg5 = 1;
if (mk % 8 == 1) neg4 = 1;
if (mk % 8 == 2) neg3 = 1;
if (mk % 8 == 3) neg2 = 1;
if (mk % 8 == 4) neg1 = 1;
mk /= 8;
}
if (neg6 && y <= 6) continue;
if (neg5 && y <= 5) continue;
if (neg4 && y <= 4) continue;
if (neg3 && y <= 3) continue;
if (neg2 && y <= 2) continue;
if (neg1 && y <= 1) continue;
if (del != n % k) continue;
mk = mask;
int l = 0;
int dig2[len] = {0};
for (int it = 0; it < k; it++) {
int r = l + y + (mk % 8 - 5);
if (r == l) {
mk /= 8;
continue;
}
int car = 0;
int i = 0;
for (int j = r - 1; j >= l; j--, i++) {
dig2[i] += (int)s[j] - '0' + car;
car = 0;
if (dig2[i] > 9) {
dig2[i] -= 10;
car = 1;
}
}
l = r;
while (car) {
dig2[i] += car;
car = 0;
if (dig2[i] > 9) {
dig2[i] -= 10;
car = 1;
}
i++;
}
mk /= 8;
}
if (comp(dig1, dig2, len)) {
for (int i = 0; i < len; i++) dig1[i] = dig2[i];
}
}
int r = len - 1;
while (dig1[r] == 0) r--;
while (r >= 0) {
cout << dig1[r];
r--;
}
cout << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3524kb
input:
2 8 1 45455151 2 1 42
output:
9696 6
result:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
input:
10 1301 6 56328399613959594774559774218276494124991536454496431869449134772679831477279356599352619469813771742358572734317965823527349354276551857226632977613336815474383422853946661428822284645652423563864641261338984158269966469425994769486371736593879954275146732544891889693921182364554588732946...