QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73966#5433. Absolute DifferencenweeksWA 2ms3648kbC++174.4kb2023-01-29 19:53:332023-01-29 19:53:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-29 19:53:36]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3648kb
  • [2023-01-29 19:53:33]
  • 提交

answer

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

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct Intervalle {
  int l, r;

  bool operator<(Intervalle other) const { return l < other.l; }
};

double sq(int x) { return x * x; }

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nAlice, nBob;
  cin >> nAlice >> nBob;
  vector<Intervalle> alice(nAlice), bob(nBob);
  for (auto &[l, r] : alice) {
    cin >> l >> r;
  }
  for (auto &[l, r] : bob) {
    cin >> l >> r;
  }
  int sumAlice = 0, sumBob = 0;
  for (auto [l, r] : alice)
    sumAlice += r - l;
  for (auto [l, r] : bob)
    sumBob += r - l;
  sort(alice.begin(), alice.end());
  sort(bob.begin(), bob.end());

  if (!sumBob) {
    swap(sumBob, sumAlice);
    swap(alice, bob);
    swap(nAlice, nBob);
  }
  dbg(sumBob, sumAlice);

  if (!sumBob and !sumAlice) {
    int sol = 0;
    int bobR = 0;
    for (auto [l, r] : bob)
      bobR += l;
    int bobL = 0;
    int curBob = 0;
    for (auto [l, r] : alice) {
      while (curBob < nBob and bob[curBob].l < l) {
        bobL += bob[curBob].l;
        bobR -= bob[curBob++].l;
      }
      sol += l * curBob - l * (nBob - curBob) + bobR - bobL;
    }
    cout << setprecision(15) << fixed << sol / (double)nBob / nAlice << endl;
    return 0;
  }

  if (!sumAlice) {
    double sol = 0;
    double intR = 0, probR = 0, probL = 0, intL = 0;
    for (auto [l, r] : bob) {
      intR += (sq(r) - sq(l)) / 2;
      probR += r - l;
    }
    int cur = 0;
    for (auto [l, r] : alice) {
      while (cur < nBob and bob[cur].l < l) {
        if (bob[cur].l == bob[cur].r) {
          ++cur;
          continue;
        }
        int nxtR = min(bob[cur].r, l);
        probL += nxtR - bob[cur].l;
        probR -= nxtR - bob[cur].l;
        intL += (sq(nxtR) - sq(bob[cur].l)) / 2;
        intR -= (sq(nxtR) - sq(bob[cur].l)) / 2;
        bob[cur].l = nxtR;
      }
      sol += (probL - probR) * l + intR - intL;
    }
    cout << setprecision(15) << fixed << sol / sumBob / nAlice << endl;
    return 0;
  }

  double probL = 0, intL = 0, probR = 0, intR = 0;
  double sol = 0;

  int posAlice = 0, posBob = 0;

  auto applyAlice = [&](int l, int r) {
    sol += probR * (sq(r) - sq(l)) / 2;
    sol -= (r - l) * intR;
    probL += r - l;
    probL += r - l;
    intL += (sq(r) - sq(l)) / 2;
  };

  auto applyBob = [&](int l, int r) {
    sol += probL * (sq(r) - sq(l)) / 2;
    sol -= (r - l) * intL;
    probR += r - l;
    intR += (sq(r) - sq(l)) / 2;
  };

  while (posAlice < nAlice or posBob < nBob) {
    if (posAlice < nAlice and alice[posAlice].l == alice[posAlice].r) {
      ++posAlice;
      continue;
    }
    if (posBob < nBob and bob[posBob].l == bob[posBob].r) {
      ++posBob;
      continue;
    }
    dbg(posAlice, posBob);
    if (posAlice == nAlice) {
      auto [l, r] = bob[posBob];
      applyBob(l, r);
      ++posBob;
    } else if (posBob == nBob) {
      auto [l, r] = alice[posAlice];
      applyAlice(l, r);
      ++posAlice;
    } else if (alice[posAlice].l < bob[posBob].l) {
      double l = alice[posAlice].l;
      double r = min(alice[posAlice].r, bob[posBob].l);
      applyAlice(l, r);
      alice[posAlice].l = r;
    } else if (bob[posBob].l < alice[posAlice].l) {
      double l = bob[posBob].l;
      double r = min(alice[posAlice].l, bob[posBob].r);
      applyBob(l, r);
      bob[posBob].l = r;
    } else {
      auto &[la, ra] = alice[posAlice];
      auto &[lb, rb] = bob[posBob];
      dbg(la, ra, rb);

      double l = la;
      double r = min(ra, rb);
      sol += 1 / 3. * (r - l) * (r - l) * (r - l);
      intL += (sq(r) - sq(l)) / 2;
      intR += (sq(r) - sq(l)) / 2;
      probL += r - l;
      probR += r - l;
      la = lb = r;
    }
  }
  dbg(sol);
  cout << setprecision(15) << fixed << sol / sumAlice / sumBob << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3520kb

input:

1 1
0 1
0 1

output:

0.333333333333333

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

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

input:

1 1
0 1
1 1

output:

0.500000000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666626930237

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1500000000.000000238418579

result:

wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '1500000000.0000002', error = '0.5000000'