oj.uz

Submission #402116

# Submission time Handle Problem Language Result Execution time Memory
402116 2021-05-11T10:48:09 Z rama_pang Nicelines (RMI20_nicelines) C++17
99.3324 / 100
 16 ms 456 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;

  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.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 2 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 292 KB Output is correct

Subtask #4
18.7242446343 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 352 KB Output is partially correct
2 Partially correct 12 ms 328 KB Output is partially correct
3 Partially correct 12 ms 332 KB Output is partially correct
4 Partially correct 11 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 304 KB Output is correct
4 Correct 3 ms 292 KB Output is correct

Subtask #6
26.6081371119 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 352 KB Output is partially correct
2 Partially correct 12 ms 328 KB Output is partially correct
3 Partially correct 12 ms 332 KB Output is partially correct
4 Partially correct 11 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 304 KB Output is correct
8 Correct 3 ms 292 KB Output is correct
9 Partially correct 16 ms 316 KB Output is partially correct
10 Partially correct 11 ms 328 KB Output is partially correct
11 Partially correct 11 ms 456 KB Output is partially correct
12 Partially correct 9 ms 328 KB Output is partially correct