oj.uz

답안 #1117408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117408 2024-11-23T14:01:04 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
71.8854 / 100
 141 ms 1600 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"

using namespace std;

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

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;
    long long B = (A + 1) * cmax + 1;
    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;
        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, mij) - my_query(A, mij - 1);
            if(abs(dif_mij - 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);
}

Compilation message

nicelines.cpp: In function 'long double my_query(long double, long double)':
nicelines.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0; i<a.size(); i++)
      |                  ~^~~~~~~~~

Subtask #1
11.0 / 11.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 2 ms 336 KB Output is correct

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 336 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

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

Subtask #4
14.9745259436 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 79 ms 1452 KB Output is partially correct
2 Partially correct 83 ms 856 KB Output is partially correct
3 Partially correct 93 ms 952 KB Output is partially correct
4 Partially correct 84 ms 980 KB Output is partially correct

Subtask #5
21.0910814752 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 39 ms 940 KB Output is partially correct
2 Partially correct 35 ms 636 KB Output is partially correct
3 Partially correct 33 ms 588 KB Output is partially correct
4 Partially correct 34 ms 676 KB Output is partially correct

Subtask #6
17.8197749523 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 79 ms 1452 KB Output is partially correct
2 Partially correct 83 ms 856 KB Output is partially correct
3 Partially correct 93 ms 952 KB Output is partially correct
4 Partially correct 84 ms 980 KB Output is partially correct
5 Partially correct 39 ms 940 KB Output is partially correct
6 Partially correct 35 ms 636 KB Output is partially correct
7 Partially correct 33 ms 588 KB Output is partially correct
8 Partially correct 34 ms 676 KB Output is partially correct
9 Partially correct 124 ms 1600 KB Output is partially correct
10 Partially correct 124 ms 1544 KB Output is partially correct
11 Partially correct 141 ms 1560 KB Output is partially correct
12 Partially correct 139 ms 1524 KB Output is partially correct