QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #1321 | #838767 | #9920. Money Game 2 | Afterlife | tarjen | Success! | 2024-12-31 21:56:37 | 2024-12-31 21:56:37 |
详细
Extra Test:
Wrong Answer
time: 747ms
memory: 14924kb
input:
1 500000 0 1 1 1 3 2 0 7 16 6 0 6 13 5 25 16 6 1 0 3 1 2 0 3 10 24 7 17 80 65 62 73 234 2 0 16 21 12 16 7 26 5 0 0 1 2 0 7 6 3 4 0 0 1 1 1 1 1 17 11 6 0 0 0 1 3 0 1 1 3 0 3 0 5 7 3 2 1 0 3 2 4 1 2 2 28 3 3 0 1 44 13 0 1 3 4 2 9 0 15 19 0 1 4 0 4 3 3 5 4 0 4 1 10 4 1 23 3 4 16 1 0 5 0 0 7 0 2 0 3 4 5...
output:
3 3 4 5 7 8 10 18 25 20 17 22 29 31 41 35 23 13 8 8 7 9 12 21 37 56 68 104 166 191 214 251 305 160 92 70 60 49 44 38 40 24 12 7 6 6 7 12 12 10 8 4 3 3 4 5 8 14 25 23 16 8 4 3 3 4 3 3 4 5 4 6 6 10 12 9 7 5 4 6 7 9 9 12 19 33 22 18 19 29 53 37 20 13 12 12 13 18 18 27 28 15 10 9 7 9 9 10 11 10 8 10 11 ...
result:
wrong answer 50270th numbers differ - expected: '683202359', found: '683202358'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #838767 | #9920. Money Game 2 | tarjen | WA | 800ms | 15148kb | C++20 | 1.9kb | 2024-12-31 21:28:22 | 2024-12-31 22:12:16 |
answer
#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> p) {
out << "(" << p.first << "," << p.second << ")";
return out;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> v) {
out << "[";
if (!v.empty()) out << v[0];
for (int i = 1; i < (int)v.size(); ++i) out << "," << v[i];
out << "]";
return out;
}
#define int long long
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
auto pre = [&](int x) { return x == 0 ? n - 1 : x - 1; };
auto nxt = [&](int x) { return x == n - 1 ? 0 : x + 1; };
vector<int> ans(n);
vector<int> g;
if (n <= 80) {
g = vector<int>(n);
iota(g.begin(), g.end(), 0);
} else {
int T = 100;
while (T--) {
g.push_back(rand() % n);
}
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y) { return a[x] > a[y]; });
for (int i = 0; i < min(100ll, n); i++) {
g.push_back(pre(id[i]));
g.push_back(id[i]);
g.push_back(nxt(id[i]));
}
}
for (auto mid : g) {
vector<int> p(n);
for (int i = mid, now = 0, tt = 0; tt < n; i = pre(i), tt++) {
now /= 2;
now += a[i];
p[i] += now;
}
for (int i = nxt(mid), now = 0, tt = 0; tt < n; i = nxt(i), tt++) {
now /= 2;
now += a[i];
p[i] += now;
}
for (int i = 0; i < n; i++) ans[i] = max(ans[i], p[i] - a[i]);
}
for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) solve();
return 0;
}