oj.uz

Submission #942889

# Submission time Handle Problem Language Result Execution time Memory
942889 2024-03-11T06:26:48 Z huutuan Nicelines (RMI20_nicelines) C++14
52.0055 / 100
 78 ms 940 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=1e-7;
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))};
}

void solve(int subtask_id, int N) {
   auto f=[&](long double t) -> long double {
      return query(3e4, t);
   };
   vector<int> va, vb;
   auto dnc=[&](auto self, long double l, long double r, long double fl, long double fr){
      long double mid=(l+r)/2;
      long double fmid=f(mid);
      if (abs((fl+fr)/2-fmid)<eps) return;
      if ((r-l)<1){
         long double c=(f(r+0.1)-fr-fl+f(l-0.1))/2;
         long double d=sqrtl(max<long double>(0.0, 0.1*0.1-c*c));
         int a=round(d/c);
         if (mid<-eps) a=-a;
         int b=round(mid-(3e4)*a);
         va.push_back(a);
         vb.push_back(b);
         return;
      }
      self(self, l, mid, fl, fmid);
      self(self, mid, r, fmid, fr);
      return;
   };
   long double l=-1e12+rand(1, 10), r=1e12-rand(1, 10);
   dnc(dnc, l, r, f(l), f(r));
   the_lines_are(va, vb);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 1 ms 432 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 440 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Correct 2 ms 696 KB Output is correct

Subtask #3
7.0 / 7.0

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

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 37 ms 684 KB Output is partially correct
2 Partially correct 32 ms 688 KB Output is partially correct
3 Partially correct 30 ms 436 KB Output is partially correct
4 Incorrect 78 ms 940 KB Incorrect
5 Halted 0 ms 0 KB -

Subtask #5
21.0055324025 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 696 KB Output is partially correct
2 Partially correct 11 ms 692 KB Output is partially correct
3 Partially correct 11 ms 448 KB Output is partially correct
4 Partially correct 14 ms 692 KB Output is partially correct

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 37 ms 684 KB Output is partially correct
2 Partially correct 32 ms 688 KB Output is partially correct
3 Partially correct 30 ms 436 KB Output is partially correct
4 Incorrect 78 ms 940 KB Incorrect
5 Halted 0 ms 0 KB -