oj.uz

Submission #1117435

# Submission time Handle Problem Language Result Execution time Memory
1117435 2024-11-23T15:14:54 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
88.6829 / 100
 110 ms 1460 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"

using namespace std;

int cmax = 1e4;
const long double eps = 1e-4;

vector<int> a, b;

map<pair<long double, long double>, bool> sel;
map<pair<long double, long double>, long double> rez_query;

long double my_query(long double A, long double B)
{
    if(!sel[ {A,B}])
    {
        sel[ {A, B}] = true;
        rez_query[ {A, B}] = query(A, B);
    }
    return rez_query[ {A, B}];
}

int aprox(long double val)
{
    return (int)(val + 0.5);
}

void divide(long long st, long long dr, long long A)
{
    if(st == dr)
    {
        long long B = st;
        if(B == 0)
        {
            a.push_back(0);
            b.push_back(B);
            return;
        }
        long double val_cos = 0.5 * (my_query(A, st + 1) - 2 * my_query(A, st) + my_query(A, st - 1));
        int cur_a = aprox(sqrt(1 - val_cos * val_cos) / val_cos);
        int cur_b = B - cur_a * A;
        if(cur_b < -cmax || cur_b > cmax)
        {
            cur_a *= (-1);
            cur_b = B - cur_a * A;
        }
        a.push_back(cur_a);
        b.push_back(cur_b);
        return;
    }
    long long mij = (st + dr) >> 1;
    long double dif_dr = my_query(A, dr + 1) - my_query(A, dr);
    long double dif_st = my_query(A, st) - my_query(A, st - 1);
    if(abs(dif_dr - dif_st) <= eps)
    {
        return;
    }
    long double dif_mij = my_query(A, mij + 1) - my_query(A, mij);
    if(abs(dif_mij - dif_st) > eps)
    {
        divide(st, mij, A);
    }
    if(abs(dif_dr - dif_mij) > eps)
    {
        divide(mij + 1, dr, A);
    }
}

void solve(int subtask_id, int n)
{
    if(subtask_id == 4)
    {
        cmax = 500;
    }
    long long A = cmax + 9;
    long long B = (A + 1) * cmax + 1;
    divide(-(A + 1) * cmax - 1, B, A);
    the_lines_are(a, b);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 592 KB Output is correct
4 Correct 4 ms 480 KB Output is correct

Subtask #4
16.3380600126 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 62 ms 968 KB Output is partially correct
2 Partially correct 59 ms 860 KB Output is partially correct
3 Partially correct 59 ms 736 KB Output is partially correct
4 Partially correct 63 ms 840 KB Output is partially correct

Subtask #5
21.4752135855 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 31 ms 584 KB Output is partially correct
2 Partially correct 35 ms 1308 KB Output is partially correct
3 Partially correct 32 ms 888 KB Output is partially correct
4 Partially correct 36 ms 592 KB Output is partially correct

Subtask #6
19.869670764 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 62 ms 968 KB Output is partially correct
2 Partially correct 59 ms 860 KB Output is partially correct
3 Partially correct 59 ms 736 KB Output is partially correct
4 Partially correct 63 ms 840 KB Output is partially correct
5 Partially correct 31 ms 584 KB Output is partially correct
6 Partially correct 35 ms 1308 KB Output is partially correct
7 Partially correct 32 ms 888 KB Output is partially correct
8 Partially correct 36 ms 592 KB Output is partially correct
9 Partially correct 108 ms 1460 KB Output is partially correct
10 Partially correct 110 ms 1404 KB Output is partially correct
11 Partially correct 91 ms 1288 KB Output is partially correct
12 Partially correct 106 ms 1376 KB Output is partially correct