oj.uz

Submission #1117434

# Submission time Handle Problem Language Result Execution time Memory
1117434 2024-11-23T15:13:33 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
88.6829 / 100
 108 ms 1772 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_mij = my_query(A, mij + 1) - my_query(A, mij);
    long double dif_st = my_query(A, st) - my_query(A, st - 1);
    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 2 ms 336 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 592 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 2 ms 504 KB Output is correct
4 Correct 3 ms 452 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 716 KB Output is correct
3 Correct 4 ms 464 KB Output is correct
4 Correct 4 ms 336 KB Output is correct

Subtask #4
16.3380600126 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 56 ms 852 KB Output is partially correct
2 Partially correct 56 ms 1008 KB Output is partially correct
3 Partially correct 60 ms 1100 KB Output is partially correct
4 Partially correct 54 ms 1772 KB Output is partially correct

Subtask #5
21.4752135855 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 30 ms 592 KB Output is partially correct
2 Partially correct 39 ms 848 KB Output is partially correct
3 Partially correct 32 ms 592 KB Output is partially correct
4 Partially correct 37 ms 792 KB Output is partially correct

Subtask #6
19.869670764 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 56 ms 852 KB Output is partially correct
2 Partially correct 56 ms 1008 KB Output is partially correct
3 Partially correct 60 ms 1100 KB Output is partially correct
4 Partially correct 54 ms 1772 KB Output is partially correct
5 Partially correct 30 ms 592 KB Output is partially correct
6 Partially correct 39 ms 848 KB Output is partially correct
7 Partially correct 32 ms 592 KB Output is partially correct
8 Partially correct 37 ms 792 KB Output is partially correct
9 Partially correct 104 ms 1664 KB Output is partially correct
10 Partially correct 102 ms 1208 KB Output is partially correct
11 Partially correct 100 ms 1084 KB Output is partially correct
12 Partially correct 108 ms 1372 KB Output is partially correct