oj.uz

답안 #1117427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117427 2024-11-23T14:56:42 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
93.0325 / 100
 74 ms 1920 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 verif_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}];
}

long double my_query(long double A, long double B)
{
    long double rez = verif_query(A, B);
    /*for(int i=0; i<a.size(); i++)
    {
        long double dist = 1.0 * abs(a[i] * A - B + b[i]) / sqrt(a[i] * a[i] + 1);
        rez -= dist;
    }
    */
    return rez;
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 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 3 ms 336 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 3 ms 592 KB Output is correct

Subtask #4
17.10851219 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 40 ms 592 KB Output is partially correct
2 Partially correct 51 ms 732 KB Output is partially correct
3 Partially correct 44 ms 1920 KB Output is partially correct
4 Partially correct 49 ms 892 KB Output is partially correct

Subtask #5
22.3290268811 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 18 ms 592 KB Output is partially correct
2 Partially correct 19 ms 592 KB Output is partially correct
3 Partially correct 18 ms 592 KB Output is partially correct
4 Partially correct 19 ms 556 KB Output is partially correct

Subtask #6
22.5949885398 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 40 ms 592 KB Output is partially correct
2 Partially correct 51 ms 732 KB Output is partially correct
3 Partially correct 44 ms 1920 KB Output is partially correct
4 Partially correct 49 ms 892 KB Output is partially correct
5 Partially correct 18 ms 592 KB Output is partially correct
6 Partially correct 19 ms 592 KB Output is partially correct
7 Partially correct 18 ms 592 KB Output is partially correct
8 Partially correct 19 ms 556 KB Output is partially correct
9 Partially correct 69 ms 1868 KB Output is partially correct
10 Partially correct 65 ms 1056 KB Output is partially correct
11 Partially correct 74 ms 860 KB Output is partially correct
12 Partially correct 69 ms 1300 KB Output is partially correct