QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308142#6648. 总投票数ckiseki#WA 574ms3752kbC++201.8kb2024-01-19 16:40:352024-01-19 16:40:36

Judging History

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

  • [2024-01-19 16:40:36]
  • 评测
  • 测评结果:WA
  • 用时:574ms
  • 内存:3752kb
  • [2024-01-19 16:40:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef local
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

int pw(int e, int p) {
  int r = 1;
  while (p--)
    r *= e;
  return r;
}

int64_t cdiv(int64_t x, int64_t y) {
  return (x + y - 1) / y;
}

int main() {
  cin.tie(nullptr) -> sync_with_stdio(false);
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    assert(s[i].size() == s[0].size());
  }

  const int L = s[0].size() - 2;
  const int C = pw(10, L);
  debug(C);

  vector<int> p(n);
  for (int i = 0; i < n; i++)
    p[i] = int(stold(s[i]) * C);

  for (int k = 1; k <= C; k++) {
    int64_t lsum = 0, rsum = 0;
    for (int i = 0; i < n; i++) {
      int64_t l = p[i] == 0 ? 0 : cdiv(k * (p[i] * 2 - 1), C * 2);
      int64_t r = cdiv(k * (p[i] * 2 + 1), C * 2) - 1;

      lsum += l;
      rsum += r;

      // P[i] - (1/2) 10^{-L} <= D[i] / K < P[i] + (1/2) 10^{-L}
      //
      // P[i] * 2C - 1 <= D[i] / K * 2C < P[i] * 2C + 1
      //
      // K * (P[i] * 2C - 1) / (2C)
    }

    if (lsum <= k && k <= rsum) {
      cout << k << '\n';
      return 0;
    }
  }
}

详细

Test #1:

score: 0
Wrong Answer
time: 574ms
memory: 3752kb

input:

100
0.009862
0.010100
0.009996
0.010052
0.009983
0.009759
0.009846
0.010008
0.010085
0.009909
0.010107
0.010161
0.010011
0.009956
0.009948
0.009979
0.010020
0.009991
0.010060
0.010080
0.009949
0.009897
0.010135
0.010042
0.010003
0.009957
0.009934
0.009838
0.010195
0.010249
0.009908
0.009959
0.010060...

output:


result:

wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements