Submission #943463

#	Time	Username	Problem	Language	Result	Execution time	Memory
943463		CDuong	Nicelines (RMI20_nicelines)	C++17	100 / 100	4 ms	948 KiB

nicelines

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include "nice_lines.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxC = 2e4;
const int EmptyLow = mxC + 1;
const int EmptyHigh = 2 * mxC - 1;
const int mod = 3 * mxC;
const long double eps = 1e-4;

struct Point {
    long double x, y;
    Point(long double x, long double y) : x(x), y(y) {}
};

struct Line {
    long double a, b;

    Line(long double a, long double b) : a(a), b(b) {}
    Line(Point p, Point q) {
        a = (q.y - p.y) / (q.x - p.x);
        b = p.y - a * p.x;
    }

    bool OnLine(Point p) {
        return abs(a * p.x + b - p.y) < eps;
    }
};

Point intersectLines(const Line& l1, const Line& l2) {
    long double x = (l2.b - l1.b) / (l1.a - l2.a);
    long double y = l1.a * x + l1.b;
    return Point(x, y);
}

long double F(long double x) { return query(mod, x); }

set<i64> res;

void dnc(Line ll, Line lr) {
    auto inter = intersectLines(ll, lr);
    i64 y = round(inter.x);
    i64 rem = (y % mod + mod) % mod;

    if (EmptyLow <= rem and rem <= EmptyHigh) {
        i64 d1 = y - (rem - EmptyLow);
        i64 d2 = y + (EmptyHigh - rem);
        Line lm(Point(d1, F(d1)), Point(d2, F(d2)));
        dnc(ll, lm); dnc(lm, lr);
        return;
    }

    i64 u1 = (rem < EmptyLow ? y + EmptyLow - rem : y + mod + EmptyLow - rem);
    i64 u2 = (rem < EmptyHigh ? y + EmptyHigh - rem : y + mod + EmptyHigh - rem);
    i64 d1 = u1 - mod, d2 = u2 - mod;

    Point Fd2 = Point(d2, F(d2));
    if (ll.OnLine(Fd2)) {
        Point Fu1 = Point(u1, F(u1));
        if (lr.OnLine(Fu1)) res.insert(y);
        else dnc(Line(Fu1, Point(u2, F(u2))), lr);
    }
    else {
        Line lm = Line(Point(d1, F(d1)), Fd2);
        dnc(ll, lm); dnc(lm, lr);
    }
}

void solve(int subtask_id, int n) {
    i64 l1 = -1ll * mod * mod - EmptyHigh;
    i64 l2 = -1ll * mod * mod - EmptyLow;
    i64 r1 = 1ll * mod * mod + EmptyLow;
    i64 r2 = 1ll * mod * mod + EmptyHigh;
    dnc(Line(Point(l1, F(l1)), Point(l2, F(l2))), Line(Point(r1, F(r1)), Point(r2, F(r2))));

    vector<int> a, b;
    for (auto y : res) {
        i64 bb = y % mod;
        if (bb < -mxC) bb += mod;
        if (bb > mxC) bb -= mod;
        i64 aa = (y - bb) / mod;
        a.push_back(aa);
        b.push_back(bb);
    }
    the_lines_are(a, b);
}

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