oj.uz

Submission #750829

# Submission time Handle Problem Language Result Execution time Memory
750829 2023-05-30T11:00:39 Z doowey Nicelines (RMI20_nicelines) C++14
11 / 100
 67 ms 312 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"

using namespace std;

typedef long double ld;
typedef pair<ld, ld> pdd;

#define fi first
#define se second
#define mp make_pair

const int X = (int)2e4 + 4;
const int B = X * 1ll * X;
const ld EPS = 1e-5;

bool on_line(ld x0, ld y0, ld x1, ld y1, ld x2, ld y2){
    return abs((x2 - x1) * (y1 - y0) - (y2 - y1) * (x1 - x0)) < EPS;
}

vector<int> aa, bb;

void solve(int lef, int rig, ld la, ld ra){
    if(la < 0.0){
        la = query(X, (ld)lef - 0.5);
    }
    if(ra < 0.0){
        ra = query(X, (ld)rig + 0.5);
    }
    if(lef == rig){
        ld ma = query(X, lef);
        if(on_line(lef - 0.5, la, lef, ma, rig + 0.5, ra)) return;
        int B = (lef % X + X) % X;
        if(B > (int)1e4) B = X - B;
        int A = (lef - B) / X;
        aa.push_back(A);
        bb.push_back(B);
        return;
    }
    int mid = lef + (rig - lef) / 2;
    ld ma = query(X, (ld)mid + 0.5);
    if(on_line(lef - 0.5, la, mid + 0.5, ma, rig + 0.5, ra)) return;
    solve(lef, mid, la, ma);
    solve(mid + 1, rig, ma, ra);

}

void solve(int subtask_id, int N) {
    /*
    printf("subtask_id = %d, N = %d\n", subtask_id, N);
    printf("query(0, 0) = %Lf\n", query(0, 0));
    printf("query(1, 1) = %Lf\n", query(1, 1));
    */
    solve(-B, B, -1.0, -1.0);
    the_lines_are(aa, bb);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 312 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 5 ms 304 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 208 KB Output is correct
2 Incorrect 9 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 292 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

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

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 292 KB Incorrect
2 Halted 0 ms 0 KB -