Submission #402116

#	Time	Username	Problem	Language	Result	Execution time	Memory
402116		rama_pang	Nicelines (RMI20_nicelines)	C++17	99.33 / 100	16 ms	456 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-5;
const lint INF = 3e9;
const lint MAXV = 1e4;
const lint BASE = 5e4;

class Line {
 public:
  ldouble a, 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) {  
  map<pair<lint, lint>, ldouble> memo;
  const auto Query = [&](lint x, lint y) {
    if (memo.count({x, y})) return memo[{x, y}];
    return memo[{x, y}] = query(x, y);
  };

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

  set<lint> changing_points;
  const auto Solve = [&](const auto &self, Line lft, Line rgt, int depth) -> void {
    // cout << lft.a << ' ' << lft.b << ' ' << rgt.a << ' ' << rgt.b << " hi\n";
    // if (depth > 10 * N) return;
    if (abs(lft.a - rgt.a) < EPS) return;
    ldouble interX_ = IntersectionX(lft, rgt);
    lint interX = round(interX_);

    Line midUp(interX, Query(BASE, interX), interX + 1, Query(BASE, interX + 1));
    Line midDn(interX, Query(BASE, interX), interX - 1, Query(BASE, interX - 1));
    if (abs(midUp.a - midDn.a) > EPS) {
      // cout << interX << ' ' << interX_ << " inter" << endl;
      // assert(abs(interX - interX_) < EPS);
      changing_points.emplace(interX);
    }
    
    self(self, lft, midDn, depth + 1);
    self(self, midUp, rgt, depth + 1);
  };

  Solve(Solve, 
        Line(-INF, Query(BASE, -INF), -INF + BASE, Query(BASE, -INF + BASE)),
        Line(+INF, Query(BASE, +INF), +INF - BASE, Query(BASE, +INF - BASE)), 0);
  
  // cout << "HUH?" << endl;

  // for (auto y : changing_points) cout << y << ' '; cout << endl;

  vector<int> answerA, answerB;
  for (auto y : changing_points) {
    // 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));    

    // cout << a << ' ' << b << " line" << endl;
  }

  return the_lines_are(answerA, answerB);
}

/*
1
17 10000 10000
1 0
2 1
3 2
3 3
4 4
4 3
4 2
4 1
0 1
0 0
0 -1
0 -2
4 -1
4 -2
-4 -4
-10000 -10000
10000 10000

1
2 1000 1000
-10000 -10000
10000 10000

*/

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