oj.uz

Submission #1117428

# Submission time Handle Problem Language Result Execution time Memory
1117428 2024-11-23T14:57:13 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
93.0325 / 100
 78 ms 1560 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"

using namespace std;

int cmax = 1e4;
long double eps;

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 solve(int subtask_id, int n)
{
    if(subtask_id == 4)
    {
        cmax = 500;
    }
    long long A = cmax + 9;
    long long B = (A + 1) * cmax + 1;
    eps = (my_query(A, B) - my_query(A, B - 1)) * 0.001;
    for(int i=0; i<n; i++)
    {
        long double dif = my_query(A, B) - my_query(A, B - 1);
        long long st = -(A + 1) * cmax - 1 + (n - 1);
        long long dr = B - 1;
        long double dif_B = 0;
        long long poz = 0;
        while(st <= dr)
        {
            long long mij = (st + dr) >> 1LL;
            long double dif_mij = my_query(A, B) - my_query(A, mij - 1);
            if(abs(dif_mij - (B - mij + 1) * dif) > eps)
            {
                poz = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }
        B = poz;
        dif_B = my_query(A, B) - my_query(A, B - 1);
        if(B == 0)
        {
            a.push_back(0);
            b.push_back(B);
        }
        else
        {
            long double val_cos = 0.5 * (dif - dif_B);
            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);
        }
    }
    the_lines_are(a, b);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 512 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 2 ms 336 KB Output is correct
2 Correct 3 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 #3
7.0 / 7.0

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

Subtask #4
17.10851219 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 48 ms 1560 KB Output is partially correct
2 Partially correct 44 ms 724 KB Output is partially correct
3 Partially correct 39 ms 1096 KB Output is partially correct
4 Partially correct 42 ms 840 KB Output is partially correct

Subtask #5
22.3290268811 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 20 ms 592 KB Output is partially correct
2 Partially correct 18 ms 592 KB Output is partially correct
3 Partially correct 18 ms 592 KB Output is partially correct
4 Partially correct 19 ms 592 KB Output is partially correct

Subtask #6
22.5949885398 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 48 ms 1560 KB Output is partially correct
2 Partially correct 44 ms 724 KB Output is partially correct
3 Partially correct 39 ms 1096 KB Output is partially correct
4 Partially correct 42 ms 840 KB Output is partially correct
5 Partially correct 20 ms 592 KB Output is partially correct
6 Partially correct 18 ms 592 KB Output is partially correct
7 Partially correct 18 ms 592 KB Output is partially correct
8 Partially correct 19 ms 592 KB Output is partially correct
9 Partially correct 69 ms 1096 KB Output is partially correct
10 Partially correct 76 ms 1120 KB Output is partially correct
11 Partially correct 78 ms 856 KB Output is partially correct
12 Partially correct 71 ms 1352 KB Output is partially correct