QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104745 | #5374. 数圈 | HgCl2 | 0 | 2ms | 3404kb | C++14 | 2.2kb | 2023-05-11 20:39:08 | 2023-05-11 20:39:12 |
Judging History
answer
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <string>
namespace {
using std::cin;
using std::cout;
using std::int64_t;
using std::size_t;
namespace base {
template <typename T, size_t... sizes>
struct NestedArray {};
template <typename T, size_t size, size_t... sizes>
struct NestedArray<T, size, sizes...> {
using Type = std::array<typename NestedArray<T, sizes...>::Type, size>;
};
template <typename T>
struct NestedArray<T> {
using Type = T;
};
template <typename T, size_t... sizes>
using Array = typename NestedArray<T, sizes...>::Type;
void OptimizeIO() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
}
void OptimizeIO(const std::string &input_file, const std::string &output_file) {
static std::ifstream input_stream(input_file);
static std::ofstream output_stream(output_file);
cin.rdbuf(input_stream.rdbuf());
cout.rdbuf(output_stream.rdbuf());
cin.tie(nullptr), cout.tie(nullptr);
}
} // namespace base
using base::Array;
const int kMaxN = 1.0e5 + 5;
int n;
int64_t ans;
Array<int, kMaxN> a, sum_a;
void Solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sum_a[0] = 0;
for (int i = 1; i <= n; i++) sum_a[i] = sum_a[i - 1] + a[i];
if (sum_a[n] < 0) {
cout << "-1\n";
return;
}
if (sum_a[n] == 0) {
if (std::count(a.begin() + 1, a.begin() + n + 1, 0) == n) {
cout << "0\n";
} else {
cout << "-1\n";
}
return;
}
int64_t ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) ans += (sum_a[i] > sum_a[j]);
}
std::sort(sum_a.begin(), sum_a.begin() + n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (sum_a[j] > sum_a[i]) break;
ans += sum_a[i] / sum_a[n] - sum_a[j] / sum_a[n];
ans -= (sum_a[i] % sum_a[n] < sum_a[j] % sum_a[n]);
}
sum_a[i]++;
}
cout << ans << "\n";
}
int Main() {
base::OptimizeIO();
int t;
cin >> t;
while (t--) Solve();
return 0;
}
} // namespace
int main() { return Main(); }
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3404kb
input:
10 3 2 -9 -4 3 4 6 0 3 3 -10 0 3 7 -6 3 3 -6 7 10 3 -3 9 -2 3 6 1 -2 3 5 2 -2 3 -9 -5 7 3 -4 -5 6
output:
-1 0 -1 3 1 3 2 1 -1 -1
result:
wrong answer 6th lines differ - expected: '4', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #4:
score: 0
Time Limit Exceeded
input:
10 30000 -3879 -556 4570 1863 2815 -4010 2471 -270 2835 3071 -3331 -1251 -2243 4221 -5249 -4134 3376 1978 858 2545 -4207 386 3875 2029 1706 1119 3065 -3097 4399 4385 -3021 2473 2506 2157 3946 -886 3929 1478 2728 -4239 4091 -151 -4762 -2136 -1424 2162 -669 267 190 -1180 2640 -757 -2078 -1409 3165 216...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%