Submission #402393

#	Time	Username	Problem	Language	Result	Execution time	Memory
402393		rama_pang	Nicelines (RMI20_nicelines)	C++17	100 / 100	15 ms	356 KiB

nicelines

#include "nice_lines.h"

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

using lint = long long;
using ldouble = long double;

const ldouble EPS = 1e-4;
const lint INF = 2.1e8;
const lint MAXV = 1e4;
const lint BASE = 2e4 + 1;

class Line {
 public:
  ldouble a, b;
  ldouble get(ldouble x) { return a * x + b; }

  Line(ldouble a, ldouble b) : a(a), b(b) {}
  Line(ldouble x1, ldouble y1, ldouble x2, ldouble y2) {
    a = (y1 - y2) / (x1 - x2);
    b = y1 - a * x1;
  }
};

void solve(int subtask_id, int N) {
  int query_count = 0;

  map<lint, ldouble> memo;
  const auto Query = [&](lint y) {
    if (memo.count(y)) return memo[y];
    query_count++;
    return memo[y] = query(BASE, ldouble(y) / 2);
  };

  const auto IntersectionX = [&](Line l1, Line l2) {
    // a1 * x + b1 = a2 * x + b2
    // x = (b2 - b1) / (a1 - a2)
    return (l2.b - l1.b) / (l1.a - l2.a);
  };

  const auto OneLine = [&](ldouble x_1, ldouble y_1, ldouble x_2, ldouble y_2, ldouble x_3, ldouble y_3) {
    return abs((y_2 - y_1) / (x_2 - x_1) - (y_3 - y_2) / (x_3 - x_2)) < 1e-11;
  };

  set<lint> changing_points;

  map<lint, ldouble> process;

  process[2 * (-INF + 0 * BASE)] = Query(2 * (-INF + 0 * BASE));
  process[2 * (-INF + 1 * BASE)] = Query(2 * (-INF + 1 * BASE));
  process[2 * (-INF + 2 * BASE)] = 2 * Query(2 * (-INF + 1 * BASE)) - Query(2 * (-INF + 0 * BASE));

  process[2 * (+INF + 0 * BASE)] = Query(2 * (+INF + 0 * BASE));
  process[2 * (+INF + 1 * BASE)] = Query(2 * (+INF + 1 * BASE));
  process[2 * (+INF + 2 * BASE)] = 2 * Query(2 * (+INF + 1 * BASE)) - Query(2 * (+INF + 0 * BASE));

  const auto IsChangingPoint = [&](lint y) {
    auto it = process.find(y);
    if (!OneLine(it->first, it->second,
                 next(it)->first, next(it)->second,
                 next(next(it))->first, next(next(it))->second)) {
      return false;
    }
    if (!OneLine(it->first, it->second,
                 prev(it)->first, prev(it)->second,
                 prev(prev(it))->first, prev(prev(it))->second)) {
      return false;
    }
    return !OneLine(prev(it)->first, prev(it)->second,
                    it->first, it->second,
                    next(it)->first, next(it)->second);
  };

  auto it = begin(process); it++; it++;
  while (next(next(it)) != end(process)) {
    lint y = it->first;

    if (IsChangingPoint(y)) {
      changing_points.emplace(y);
      it++;
      continue;
    }

    if (OneLine(it->first, it->second,
                next(it)->first, next(it)->second,
                next(next(it))->first, next(next(it))->second)) {
      it++;
      continue;
    }

    if (OneLine(prev(it)->first, prev(it)->second,
                it->first, it->second,
                next(it)->first, next(it)->second)) {
      it++;
      continue;
    }

    lint isect;

    {
      auto it0 = prev(it);
      auto it1 = it;
      auto it2 = next(it);
      auto it3 = next(next(it));

      lint lo = it1->first + 1;
      lint hi = it2->first - 1;
      while (lo < hi) {
        lint md = (lo + hi) >> 1;
        ldouble yprv = it0->second + ((it1->second - it0->second) / (it1->first - it0->first)) * (md - it0->first);
        ldouble ynxt = it3->second + ((it2->second - it3->second) / (it2->first - it3->first)) * (md - it3->first);
        if (yprv <= ynxt + EPS) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }
      isect = lo;
    }

    if (process.count(isect) == 0) {
      process[isect] = Query(isect);
    } else {
      process[y + 1] = Query(y + 1);
      process[y + 2] = Query(y + 2);
    }

    it = process.find(y);
  }

  assert(changing_points.size() == N);

  vector<int> answerA, answerB;
  for (auto y : changing_points) {
    y >>= 1;

    // y = ax + b
    // x = BASE
    // b = y % BASE

    lint b = y % BASE;
    while (b < -MAXV) b += BASE;
    while (b > +MAXV) b -= BASE;

    assert((y - b) % BASE == 0);
    lint a = (y - b) / BASE;

    assert(-MAXV <= a && a <= +MAXV);
    assert(-MAXV <= b && b <= +MAXV);

    answerA.emplace_back(int(a));
    answerB.emplace_back(int(b));
  }

  assert(query_count <= 3 * N + 2);
  return the_lines_are(answerA, answerB);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from nicelines.cpp:3:
nicelines.cpp: In function 'void solve(int, int)':
nicelines.cpp:132:33: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |   assert(changing_points.size() == N);
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~
nicelines.cpp:36:14: warning: variable 'IntersectionX' set but not used [-Wunused-but-set-variable]
   36 |   const auto IntersectionX = [&](Line l1, Line l2) {
      |              ^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27