oj.uz

답안 #1117407

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117407 2024-11-23T13:58:45 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
45.7002 / 100
 98 ms 2292 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"

using namespace std;

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

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 = 2 * 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 592 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 456 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 592 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Correct 3 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 5 ms 336 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 4 ms 336 KB Output is correct

Subtask #4
14.7001562821 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 97 ms 1836 KB Output is partially correct
2 Partially correct 98 ms 1228 KB Output is partially correct
3 Partially correct 96 ms 1292 KB Output is partially correct
4 Partially correct 97 ms 2292 KB Output is partially correct

Subtask #5
0.0 / 23.0

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

Subtask #6
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 97 ms 1836 KB Output is partially correct
2 Partially correct 98 ms 1228 KB Output is partially correct
3 Partially correct 96 ms 1292 KB Output is partially correct
4 Partially correct 97 ms 2292 KB Output is partially correct
5 Incorrect 20 ms 604 KB Incorrect
6 Halted 0 ms 0 KB -