Submission #743135

#	Time	Username	Problem	Language	Result	Execution time	Memory
743135		maomao90	Nicelines (RMI20_nicelines)	C++17	70.53 / 100	153 ms	752 KiB

nicelines

#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));
}

ld mp0[MAXA * 4 + 5];
ld query0(int x) {
    /*
    if (mp0[x + MAXA] != LINF) {
        return mp0[x + MAXA];
    }
    return mp0[x + MAXA] = query(0, x);
    */
    return query(0, x);
}

int fib[MAXA];
void solve(int subtask_id, int n) {
    REP (i, 0, MAXA * 2) {
        mp0[i] = LINF;
    }
    vi va, vb;
    vector<Line> vl;
    int blo = -MAXA, bhi = MAXA;
    if (subtask_id == 4) {
        blo = -500, bhi = 500;
    }
    fib[0] = 1; fib[1] = 2;
    int gd = -1;
    REP (i, 2, MAXA) {
        fib[i] = fib[i - 1] + fib[i - 2];
        if (blo + fib[i] >= bhi) {
            bhi = blo + fib[i];
            gd = i;
            break;
        }
    }
    REP (i, 0, n) {
        int lo = blo, hi = bhi;
        RREP (k, gd, 2) {
        //while (hi - lo >= 3) {
            //int mid1 = lo + (hi - lo) / 3, mid2 = lo + (hi - lo) / 3 * 2;
            int mid1 = lo + fib[k - 2], mid2 = lo + fib[k - 1];
            ld q1 = query0(mid1), q2 = query0(mid2);
            cerr << mid1 << ": " << q1 << '\n';
            cerr << ' ' << mid2 << ": " << q2 << '\n';
            for (Line l : vl) {
                q1 -= l.dist(Point(0, mid1));
                q2 -= l.dist(Point(0, mid2));
            }
            //cerr << mid1 << ": " << q1 << '\n';
            //cerr << ' ' << mid2 << ": " << q2 << '\n';
            if (q1 < q2) {
                hi = mid2;
            } else {
                lo = mid1;
            }
        }
        int b = INF;
        ld mn = LINF;
        REP (i, lo, hi + 1) {
            ld q = query0(i);
            for (Line l : vl) {
                q -= l.dist(Point(0, i));
            }
            if (mnto(mn, q)) {
                b = i;
            }
        }
        //assert(b != INF);
        lo = -MAXA, hi = MAXA;
        if (subtask_id == 4) {
            lo = -500, hi = 500;
        }
        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);
            //cerr << mid1 << ' ' << mid1 * STEP + b << ": " << q1 << '\n';
            //cerr << ' ' << mid2 << ' ' << mid2 * STEP + b << ": " << q2 << '\n';
            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) {
            ld q = query(STEP, i * STEP + b);
            for (Line l : vl) {
                q -= l.dist(Point(STEP, i * STEP + b));
            }
            if (mnto(mn, q)) {
                a = i;
            }
        }
        //assert(a != INF);
        va.pb(a); vb.pb(b);
        vl.pb(Line(a, b));
    }
    the_lines_are(va, vb);
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 10.6386538861 / 19
• Subtask 5: 19.0680975209 / 23
• Subtask 6: 9.8249843727 / 27