Submission #402585

#	Time	Username	Problem	Language	Result	Execution time	Memory
402585		rama_pang	Nicelines (RMI20_nicelines)	C++17	100 / 100	7 ms	328 KiB

nicelines

#include "nice_lines.h"

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

using lint = long long;
using ldouble = long double;
using point = pair<lint, ldouble>;

const ldouble EPS = 1e-9;
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 = [&](lint x_1, lint x_2, lint x_3) {
    if (x_1 == x_2 || x_1 == x_3 || x_2 == x_3) return true;
    ldouble y_1 = Query(x_1), y_2 = Query(x_2), y_3 = Query(x_3);
    return abs((y_2 - y_1) / (x_2 - x_1) - (y_3 - y_2) / (x_3 - x_2)) < EPS;
  };

  set<lint> changing_points;
  const auto Solve = [&](const auto &self, lint lft1, lint lft2, lint rgt1, lint rgt2) {
    Line lftLine(lft1, Query(lft1), lft2, Query(lft2));
    Line rgtLine(rgt1, Query(rgt1), rgt2, Query(rgt2));
    if (abs(lftLine.a - rgtLine.a) < EPS) return;
    lint midX = round(IntersectionX(lftLine, rgtLine));
    if (OneLine(lft1, lft2, midX) && OneLine(midX, rgt1, rgt2)) {
      // Since the function is concave, this must be the last changing point between lft and rgt
      // Since otherwise, the y-value of midX must be higher
      // For each changing point, we query 1 time
      // There are N changing points, so we query N times
      changing_points.emplace(midX);
    } else {
      // The y-value of midX is higher than the intersection point of lft and rgt
      // Thus, midX must be on a line segment
      // For each line segment, we will count it 2 times
      // There are (N + 1) line segments, so we query a total of 2N + 2 times
      self(self, lft1, lft2, midX - 1, midX);
      self(self, midX - 1, midX, rgt1, rgt2);
    }
  };

  Solve(Solve, 2 * (-INF), 2 * (-INF + BASE), 2 * (+INF), 2 * (+INF + BASE));
  assert(changing_points.size() == N);

  vector<int> answerA, answerB;
  for (auto y : changing_points) {
    assert(y % 2 == 0); y /= 2;

    // 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));
  }

  // N for changing points + 2 * (N + 1) for line segments = 3N + 2
  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:71:33: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |   assert(changing_points.size() == N);
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~

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