QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#494186 | #9133. Function with Many Maximums | ucup-team004# | AC ✓ | 22ms | 10880kb | C++20 | 1.6kb | 2024-07-27 14:37:36 | 2024-07-27 14:37:36 |
Judging History
answer
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
constexpr int B = 100000;
int b;
std::cin >> b;
assert(b <= B);
i64 sum = 0;
constexpr int N = 5 * B;
constexpr int T = 1000;
std::vector<i64> a(N);
for (int i = 0; i < N; i++) {
if (8E22 / (i + 1) / (i + 2) > 1E12 - i) {
a[i] = 1E12 - i;
} else {
a[i] = 8E22 / (i + 1) / (i + 2);
}
}
std::vector<i64> f(N);
sum = 0;
for (int i = 0; i < N; i++) {
f[i] = (i + 2) * a[i] + sum;
if (i >= N - 2 * B && f[i] - f[i - 1] < 0) {
i64 t = f[i - 1] - f[i];
a[i] += t / (i + 2) + 1;
f[i] = (i + 2) * a[i] + sum;
}
sum += a[i];
}
for (int i = 1; i < N; i++) {
assert(a[i] < a[i - 1]);
}
for (int i = N - 2; i >= N - 2 * B; i -= 2) {
if (a[i] - (f[i + 1] - f[i - 1]) > a[i + 1]) {
a[i] -= (f[i + 1] - f[i - 1]);
} else {
assert(false);
}
}
for (int i = N - 2 * B - 1; i >= 0; i--) {
a[i] = a[i + 1] + 1;
}
sum = 0;
for (int i = 0; i < N; i++) {
f[i] = (i + 2) * a[i] + sum;
sum += a[i];
}
for (int i = 1; i < N; i++) {
assert(a[i] < a[i - 1]);
}
std::cout << N << "\n";
for (int i = 0; i < N; i++) {
std::cout << a[i] << " \n"[i == N - 1];
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 20ms
memory: 10848kb
input:
4
output:
500000 888879977214 888879977213 888879977212 888879977211 888879977210 888879977209 888879977208 888879977207 888879977206 888879977205 888879977204 888879977203 888879977202 888879977201 888879977200 888879977199 888879977198 888879977197 888879977196 888879977195 888879977194 888879977193 8888799...
result:
ok n=500000, max_a=888879977214, max_num=100000 >= 4
Test #2:
score: 0
Accepted
time: 22ms
memory: 10880kb
input:
100000
output:
500000 888879977214 888879977213 888879977212 888879977211 888879977210 888879977209 888879977208 888879977207 888879977206 888879977205 888879977204 888879977203 888879977202 888879977201 888879977200 888879977199 888879977198 888879977197 888879977196 888879977195 888879977194 888879977193 8888799...
result:
ok n=500000, max_a=888879977214, max_num=100000 >= 100000
Extra Test:
score: 0
Extra Test Passed