oj.uz

Submission #402186

# Submission time Handle Problem Language Result Execution time Memory
402186 2021-05-11T12:04:59 Z rama_pang Nicelines (RMI20_nicelines) C++17
99.4371 / 100
 17 ms 376 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 288 KB Output is correct

Subtask #4
18.7935299013 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 316 KB Output is partially correct
2 Partially correct 8 ms 352 KB Output is partially correct
3 Partially correct 17 ms 312 KB Output is partially correct
4 Partially correct 10 ms 328 KB Output is partially correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Output is correct
2 Correct 4 ms 200 KB Output is correct
3 Correct 4 ms 316 KB Output is correct
4 Correct 2 ms 316 KB Output is correct

Subtask #6
26.6435819964 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 316 KB Output is partially correct
2 Partially correct 8 ms 352 KB Output is partially correct
3 Partially correct 17 ms 312 KB Output is partially correct
4 Partially correct 10 ms 328 KB Output is partially correct
5 Correct 4 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 4 ms 316 KB Output is correct
8 Correct 2 ms 316 KB Output is correct
9 Partially correct 12 ms 376 KB Output is partially correct
10 Partially correct 11 ms 324 KB Output is partially correct
11 Partially correct 11 ms 344 KB Output is partially correct
12 Partially correct 12 ms 336 KB Output is partially correct