oj.uz

Submission #1117416

# Submission time Handle Problem Language Result Execution time Memory
1117416 2024-11-23T14:09:41 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
73.0325 / 100
 75 ms 1692 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 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;
    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);
}

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

# 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 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 336 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
17.10851219 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 49 ms 1020 KB Output is partially correct
2 Partially correct 47 ms 816 KB Output is partially correct
3 Partially correct 46 ms 808 KB Output is partially correct
4 Partially correct 44 ms 948 KB Output is partially correct

Subtask #5
22.3290268811 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 21 ms 496 KB Output is partially correct
2 Partially correct 18 ms 592 KB Output is partially correct
3 Partially correct 21 ms 732 KB Output is partially correct
4 Partially correct 21 ms 784 KB Output is partially correct

Subtask #6
22.5949885398 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 49 ms 1020 KB Output is partially correct
2 Partially correct 47 ms 816 KB Output is partially correct
3 Partially correct 46 ms 808 KB Output is partially correct
4 Partially correct 44 ms 948 KB Output is partially correct
5 Partially correct 21 ms 496 KB Output is partially correct
6 Partially correct 18 ms 592 KB Output is partially correct
7 Partially correct 21 ms 732 KB Output is partially correct
8 Partially correct 21 ms 784 KB Output is partially correct
9 Partially correct 75 ms 900 KB Output is partially correct
10 Partially correct 66 ms 932 KB Output is partially correct
11 Partially correct 71 ms 1692 KB Output is partially correct
12 Partially correct 63 ms 840 KB Output is partially correct