QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#104745#5374. 数圈HgCl20 2ms3404kbC++142.2kb2023-05-11 20:39:082023-05-11 20:39:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-11 20:39:12]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3404kb
  • [2023-05-11 20:39:08]
  • 提交

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%