oj.uz

Submission #742997

# Submission time Handle Problem Language Result Execution time Memory
742997 2023-05-17T07:18:19 Z maomao90 Nicelines (RMI20_nicelines) C++17
11 / 100
 163 ms 304 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if(0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 100;
const int MAXA = 10000;
const ld EPS = 1e-12;
const ld STEP = 1e-5;

struct Point {
    long double x, y;
    Point();
    Point(long double x, long double y);
    Point operator-() const;
    Point& operator+=(const Point &p);
    Point& operator-=(const Point &p);
    Point operator+(const Point &p) const;
    Point operator-(const Point &p) const;
    Point operator* (long double k) const;
    long double dot(const Point &p) const;
};
struct Line {
    Point off, dir;
    Line(int a, int b);
    long double dist(Point p);
};
Point::Point(): x(0), y(0) {}
Point::Point(long double x, long double y): x(x), y(y) {}
Point Point::operator-() const{
    return Point(-x, -y);
}
Point& Point::operator+=(const Point &p) {
    x += p.x;
    y += p.y;
    return *this;
}
Point& Point::operator-=(const Point &p) {
    return *this += (-p);
}
Point Point::operator+(const Point &p) const {
    Point res = *this;
    return res += p;
}
Point Point::operator-(const Point &p) const {
    Point res = *this;
    return res -= p;
}
long double Point::dot(const Point &p) const {
    return x * p.x + y * p.y;
}
Point Point::operator* (long double k) const {
    return Point(x * k, y * k);
}

Line::Line(int a, int b) {
    off = Point(0, b);
    dir = Point(1, a);
}
long double Line::dist(Point p) {
    p -= off;
    Point delta = dir * (p.dot(dir) / dir.dot(dir)) - p;
    return sqrt(delta.dot(delta));
}

void solve(int subtask_id, int n) {
    vi va, vb;
    vector<Line> vl;
    REP (i, 0, n) {
        int lo = -MAXA, hi = MAXA;
        while (hi - lo >= 3) {
            int mid1 = lo + (hi - lo) / 3, mid2 = lo + (hi - lo) / 3 * 2;
            ld q1 = query(0, mid1), q2 = query(0, mid2);
            for (Line l : vl) {
                q1 -= l.dist(Point(0, mid1));
                q2 -= l.dist(Point(0, mid2));
            }
            if (q1 < q2) {
                hi = mid2;
            } else {
                lo = mid1;
            }
        }
        int b = INF;
        ld mn = LINF;
        REP (i, lo, hi + 1) {
            if (mnto(mn, query(0, i))) {
                b = i;
            }
        }
        assert(b != INF);
        lo = -MAXA, hi = MAXA;
        while (hi - lo >= 3) {
            int mid1 = lo + (hi - lo) / 3, mid2 = lo + (hi - lo) / 3 * 2;
            ld q1 = query(STEP, mid1 * STEP + b), q2 = query(STEP, mid2 * STEP + b);
            for (Line l : vl) {
                q1 -= l.dist(Point(STEP, mid1 * STEP + b));
                q2 -= l.dist(Point(STEP, mid2 * STEP + b));
            }
            if (q1 < q2) {
                hi = mid2;
            } else {
                lo = mid1;
            }
        }
        int a = INF;
        mn = LINF;
        REP (i, lo, hi + 1) {
            if (mnto(mn, query(STEP, i * STEP + b))) {
                a = i;
            }
        }
        assert(a != INF);
        va.pb(a); vb.pb(b);
        vl.pb(Line(a, b));
    }
    the_lines_are(va, vb);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 304 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 296 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 296 KB Incorrect
2 Halted 0 ms 0 KB -