oj.uz

Submission #943462

# Submission time Handle Problem Language Result Execution time Memory
943462 2024-03-11T13:51:03 Z CDuong Nicelines (RMI20_nicelines) C++17
100 / 100
 5 ms 1200 KB 
/*
#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) {}

    friend ostream & operator << (ostream &out, const Point &p) {
        return out << "{" << p.x << ", " << p.y << "}" << endl;
    }
};

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

    friend ostream & operator << (ostream &out, const Line &l) {
        return out << l.a << "x + " << l.b;
    }
};

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

int cnt;

// long double query(long double x, long double y) { return 0.0L; }

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

set<i64> res;

void dnc(Line ll, Line lr) {
    // if (++cnt >= 5) return;
    // cout << ll << endl << lr << endl;
    // cout << ll << " " << lr << endl;
    auto inter = intersectLines(ll, lr);
    i64 y = round(inter.x);
    // cout << y << endl;
    // return;
    i64 rem = (y % mod + mod) % mod;
    // cout << rem << endl;

    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;

    // cout << d1 << " " << u1 << " " << d2 << " " << u2 << endl;
    // return;

    Point Fd2 = Point(d2, F(d2));
    // cout << Fd2 << endl;
    if (ll.OnLine(Fd2)) {
        Point Fu1 = Point(u1, F(u1));
        // cout << Fu1 << endl;
        // return;
        if (lr.OnLine(Fu1)) res.insert(y);
        else dnc(Line(Fu1, Point(u2, F(u2))), lr);
    }
    else {
        // cout << "trolled" << endl;
        // return;
        Line lm = Line(Point(d1, F(d1)), Fd2);
        // cout << lm << endl;
        dnc(ll, lm); dnc(lm, lr);
    }
}

void solve(int subtask_id, int n) {
    cout << fixed << setprecision(12);
    i64 l1 = -1ll * mod * mod - EmptyHigh;
    // cout << F(l2) << endl;
    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))));
    // dnc(Line(-1.451158241278, 240305.953013565319), Line(-1.442833588481, 480305.954147797289));

    // long long lowY1 = -1LL * MaxX * MaxX - Rest2;
    // long double lowVal1 = query(MaxX, lowY1);
    // long long lowY2 = -1LL * MaxX * MaxX - Rest1;
    // long double lowVal2 = query(MaxX, lowY2);
    // Line lowLine(lowY1, lowVal1, lowY2, lowVal2);
 
    // long long highY1 = 1LL * MaxX * MaxX + Rest1;
    // long double highVal1 = query(MaxX, highY1);
    // long long highY2 = 1LL * MaxX * MaxX + Rest2;
    // long double highVal2 = query(MaxX, highY2);
    // Line highLine(highY1, highVal1, highY2, highVal2);
 
    // divide(lowLine, highLine);
    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);
}

// int main() {
//     cout << -1 << endl;
// }

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 948 KB Output is correct
2 Correct 3 ms 692 KB Output is correct
3 Correct 3 ms 1200 KB Output is correct
4 Correct 5 ms 692 KB Output is correct

Subtask #5
23.0 / 23.0

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

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 948 KB Output is correct
2 Correct 3 ms 692 KB Output is correct
3 Correct 3 ms 1200 KB Output is correct
4 Correct 5 ms 692 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 2 ms 432 KB Output is correct
8 Correct 1 ms 688 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 3 ms 948 KB Output is correct
11 Correct 3 ms 692 KB Output is correct
12 Correct 3 ms 944 KB Output is correct