QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#430933#5433. Absolute Differenceucup-team859#WA 1ms4068kbC++145.5kb2024-06-04 18:23:202024-06-04 18:23:20

Judging History

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

  • [2024-06-04 18:23:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4068kb
  • [2024-06-04 18:23:20]
  • 提交

answer

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

using ld = long double;
using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

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

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

ld calc_exp(pair<int, int> a, pair<int, int> b, int ta, int tb) {
  if (a.second > b.second)  {
    swap(a, b);
    swap(ta, tb);
  }

  if (a == b) {
    return (a.second - a.first) / 3.0 * (a.second - a.first) / ta;
  }

  if (a.second <= b.first) {
    return (b.second - b.first) / 2.0 * (b.second - b.first) / tb - (a.second - a.first) / 2.0 * (a.second - a.first) / ta;
  }

  if (a.first >= b.first) {
    return calc_exp(a, make_pair(b.first, a.first), ta, tb)
         + calc_exp(a, a, ta, tb)
         + calc_exp(a, make_pair(a.second, b.second), ta, tb);
  }

  return calc_exp(make_pair(a.first, b.first), b, ta, tb)
       + calc_exp(make_pair(b.first, a.second), make_pair(b.first, a.second), ta, tb)
       + calc_exp(make_pair(b.first, a.second), make_pair(a.second, b.second), ta, tb);
}

vector<pair<int, int>> remove_bad(vector<pair<int, int>> &v) {
  vector<pair<int, int>> nv;

  for (auto it : v) {
    if (it.first != it.second)
      nv.push_back(it);
  }

  return nv;
}

void solve() {
  int n, m;
  cin >> n >> m;

  vector<pair<int, int>> a(n), b(m);

  ld ta = 0, tb = 0;
  for (auto &it : a) {
    cin >> it.first >> it.second;
    ta += it.second - it.first;
  }
  
  for (auto &it : b) {
    cin >> it.first >> it.second;
    tb += it.second - it.first;
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  if (ta == 0) {
    swap(a, b);
    swap(ta, tb);
    swap(n, m);
  }

  if (ta == 0 && tb == 0) {
    ld sb = 0, pfb = 0;
    for (auto it : b)
      sb += it.first;

    int j = 0;
    long double ans = 0;
    for (int i = 0; i < a.size(); ++i) {
      while (j < m && b[j].first < a[i].first) {
        sb -= b[j].first;
        pfb += b[j].first;
        ++j;
      }

      ans += a[i].first * j - pfb; 
      ans += sb - a[i].first * (m - j); 
    }  

    cout << fixed << setprecision(18) << ans / (n * m) << "\n";
    return;
  }

  if (tb == 0) {
    ld sb = 0, pfb = 0;
    for (auto it : b)
      sb += it.first;

    int j = 0;
    long double ans = 0;
    for (int i = 0; i < a.size(); ++i) {
      ld exp = (a[i].second - a[i].first) / 2.0 * (a[i].second - a[i].first) / ta;
      ld w = (a[i].second - a[i].first) / ta;

      while (j < m && b[j].first < a[i].first) {
        sb -= b[j].first;
        pfb += b[j].first;
        ++j;
      }
      ans += w * (exp * j - pfb);
      
      while (j < m && b[j].first < a[i].second) {
        sb -= b[j].first;
        pfb += b[j].first;

        ans += (b[j].first - a[i].first) / 2.0 * (b[j].first - a[i].first) / ta;
        ans += (a[i].second - b[j].first) / 2.0 * (a[i].second - b[j].first) / ta;
        ++j;
      }

      ans += w * (sb - exp * (m - j));
    }  

    cout << fixed << setprecision(18) << ans / m << "\n";
    return;
  }

  a = remove_bad(a);
  b = remove_bad(b);

  n = a.size();
  m = b.size();

  vector<pair<ld, ld>> sf(m), pf(m);
  for (int i = m - 1; i >= 0; --i) {
    sf[i].first = (b[i].second - b[i].first) / 2.0 * (b[i].second - b[i].first) / tb;
    sf[i].second = (b[i].second - b[i].first) / tb;

    if (i + 1 < m) {
      sf[i].first += sf[i + 1].first;
      sf[i].second += sf[i + 1].second;
    }
  }

  for (int i = m - 1; i >= 0; --i) {
    pf[i].first = (b[i].second - b[i].first) / 2.0 * (b[i].second - b[i].first) / tb;

    if (i - 1 >= 0) {
      pf[i].first += pf[i - 1].first;
      pf[i].second += pf[i - 1].second;
    }
  }

  int i = 0;
  ld ans = 0;
  for (auto it : a) {
    while (i < b.size() && b[i].second <= it.first) {
      ++i;
    }

    int i2 = i;
    while (i2 < b.size() && b[i2].first <= it.second) {
      ans += calc_exp(it, b[i2], ta, tb);
      ++i2;
    }

    ld exp = (it.second - it.first) / 2.0 * (it.second - it.first) / ta;
    ld w = (it.second - it.first) / ta;

    if (i > 0) {
      ans += w * (exp * pf[i - 1].second - pf[i - 1].first);
    }

    if (i2 < b.size()) {
      ans += w * (-exp * sf[i2].second + sf[i2].first);
    }
  }

  cout << fixed << setprecision(18) << ans << "\n";
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t = 1;
//  cin >> t;
  while (t--)
    solve();

  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4068kb

input:

1 1
0 1
0 1

output:

0.333333333333333315

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

1 1
0 1
1 1

output:

0.500000000000000000

result:

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

Test #3:

score: 0
Accepted
time: 1ms
memory: 3784kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666626930236816

result:

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

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3856kb

input:

1 1
-1000000000 0
0 1000000000

output:

0.000000000000000000

result:

wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '0.0000000', error = '1.0000000'