QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308144#6648. 总投票数ckiseki#WA 542ms3876kbC++201.8kb2024-01-19 16:41:562024-01-19 16:41:57

Judging History

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

  • [2024-01-19 16:41:57]
  • 评测
  • 测评结果:WA
  • 用时:542ms
  • 内存:3876kb
  • [2024-01-19 16:41:56]
  • 提交

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<int64_t> p(n);
  for (int i = 0; i < n; i++)
    p[i] = int64_t(stold(s[i]) * C);

  for (int64_t 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;
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 542ms
memory: 3640kb

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:

942983

result:

ok 1 number(s): "942983"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

100
0.0
0.1
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.1
0.0
0.1
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.1
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

100
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0.01
0...

output:

100

result:

ok 1 number(s): "100"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

20
0.060
0.070
0.000
0.030
0.070
0.060
0.040
0.040
0.030
0.040
0.050
0.050
0.070
0.060
0.100
0.040
0.060
0.060
0.040
0.030

output:

100

result:

ok 1 number(s): "100"

Test #5:

score: -100
Wrong Answer
time: 6ms
memory: 3644kb

input:

100
0.0103
0.0102
0.0086
0.0114
0.0102
0.0087
0.0095
0.0104
0.0106
0.0105
0.0089
0.0111
0.0085
0.0103
0.0112
0.0111
0.0106
0.0103
0.0101
0.0089
0.0092
0.0085
0.0113
0.0096
0.0103
0.0096
0.0104
0.0110
0.0090
0.0116
0.0104
0.0106
0.0110
0.0112
0.0081
0.0103
0.0114
0.0097
0.0101
0.0100
0.0086
0.0099
0....

output:

9607

result:

wrong answer 1st numbers differ - expected: '9703', found: '9607'