Submission #402186

#	Time	Username	Problem	Language	Result	Execution time	Memory
402186		rama_pang	Nicelines (RMI20_nicelines)	C++17	99.44 / 100	17 ms	376 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;
  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) {  
  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) -> void {
    // cout << lft.a << ' ' << lft.b << ' ' << rgt.a << ' ' << rgt.b << " hi\n";
    if (abs(lft.a - rgt.a) < EPS) return;
    ldouble interX_ = IntersectionX(lft, rgt);
    ldouble interY_ = lft.get(interX_);
    assert(abs(lft.get(interX_) - rgt.get(interX_)) < EPS);
    lint interX = round(interX_);

    if (abs(Query(BASE, interX) - interY_) < EPS) {
      changing_points.emplace(interX);
    } else {
      // another line exist between lft and rgt
      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);
      self(self, midUp, rgt);
    }


    // 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);
    // self(self, midUp, rgt);
  };

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

  // for (auto y : changing_points) cout << y << ' '; cout << endl;
  assert(changing_points.size() == N);

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

  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
4 1000 1000
-10000 -10000
-5000 -5000
5000 5000
10000 10000

1
2 1000 1000
-10000 -10000
-5000 -5000

1 - 0.7 * ANS / (10000 - 402) = 0.985486

(1 - 0.985486) * (10000 - 402) / 0.7
ANS = 199

Queries = 601

*/

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:82:33: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |   assert(changing_points.size() == N);
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~

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