oj.uz

Submission #943428

# Submission time Handle Problem Language Result Execution time Memory
943428 2024-03-11T13:08:36 Z vjudge1 Nicelines (RMI20_nicelines) C++14
100 / 100
 7 ms 992 KB 
#include "nice_lines.h"

#include <bits/stdc++.h>

using namespace std;

template<class T>
struct Point{
   T x, y;
   Point (T _x=0, T _y=0){
      x=_x; y=_y;
   }
   bool operator<(Point a){ return tie(x, y)<tie(a.x, a.y); }
   bool operator==(Point a){ return tie(x, y)==tie(a.x, a.y); }
   Point operator+(Point a){ return Point(x+a.x, y+a.y); }
   Point operator-(Point a){ return Point(x-a.x, y-a.y); }
   Point operator*(T a){ return Point(x*a, y*a); }
   Point operator/(T a){ return Point(x/a, y/a); }
   T dot(Point a){ return x*a.x+y*a.y; }
   T dot(Point a, Point b){ return (a-*this).dot(b-*this); }
   T cross(Point a){ return x*a.y-y*a.x; }
   T cross(Point a, Point b){ return (a-*this).cross(b-*this); }
   T dist2(){ return x*x+y*y; }
   long double dist(){ return sqrt(dist2()); }
};

const long double eps=3e-11;
using pt=Point<long double>;

long double line_point_dist(pt a, pt b, pt c){
   return abs(a.cross(b, c))/(a-b).dist();
}

mt19937 rng(69420);

long double rand(long double l, long double r){
   return uniform_real_distribution<long double>(l, r)(rng);
}

pair<int, int> line_from_points(pt a, pt b){
   long double slope=round((b.y-a.y)/(b.x-a.x));
   return {(int)(round(slope)), (int)(round(a.y-a.x*slope))};
}

const int X=3e4;

void solve(int subtask_id, int N) {
   vector<int> va, vb;
   vector<long double> diff;
   for (int i=0; i<=(int)1e4; ++i) diff.push_back((long double)2/sqrtl(i*i+1));
   auto insert_line=[&](int x){
      int b=x%X;
      if (b<0) b+=X;
      if (b>1e4) b-=X;
      int a=(x-b)/X;
      va.push_back(a);
      vb.push_back(b);
   };
   map<int, long double> memo;
   auto fake_query=[&](int x) -> long double {
      if (memo.count(x)) return memo[x];
      return memo[x]=query(X, x);
   };
   auto get_slope=[&](int x) -> long double {
      return fake_query(x+1)-fake_query(x);
   };
   auto dnc=[&](auto self, int l, int r, long double sl, long double sr){
      if (l==r || abs(sr-sl)<eps) return;
      for (auto &x:diff){
         if (abs(sr-sl-x)<eps){
            long double t1=fake_query(l), t2=fake_query(r);
            insert_line(round((t2-t1+l*sl-r*sr)/(sl-sr)));
            return;
         }
      }
      int mid=(l+r)>>1;
      long double smid=get_slope(mid);
      self(self, l, mid, sl, smid);
      self(self, mid, r, smid, sr);
   };
   int l=-3.3e8, r=3.3e8;
   dnc(dnc, l, r, get_slope(l), get_slope(r));
   the_lines_are(va, vb);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 740 KB Output is correct
2 Correct 5 ms 736 KB Output is correct
3 Correct 5 ms 992 KB Output is correct
4 Correct 7 ms 988 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 736 KB Output is correct
2 Correct 2 ms 732 KB Output is correct
3 Correct 3 ms 988 KB Output is correct
4 Correct 2 ms 740 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 740 KB Output is correct
2 Correct 5 ms 736 KB Output is correct
3 Correct 5 ms 992 KB Output is correct
4 Correct 7 ms 988 KB Output is correct
5 Correct 3 ms 736 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 3 ms 988 KB Output is correct
8 Correct 2 ms 740 KB Output is correct
9 Correct 7 ms 732 KB Output is correct
10 Correct 6 ms 736 KB Output is correct
11 Correct 6 ms 736 KB Output is correct
12 Correct 6 ms 732 KB Output is correct