oj.uz

Submission #1117397

# Submission time Handle Problem Language Result Execution time Memory
1117397 2024-11-23T13:45:53 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
84.1297 / 100
 144 ms 1968 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 = 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;
        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)
            {
                dif_B = dif_mij;
                B = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 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 2 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 592 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 3 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 3 ms 464 KB Output is correct

Subtask #3
7.0 / 7.0

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

Subtask #4
14.7001562821 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 87 ms 1212 KB Output is partially correct
2 Partially correct 90 ms 1652 KB Output is partially correct
3 Partially correct 94 ms 1048 KB Output is partially correct
4 Partially correct 97 ms 1332 KB Output is partially correct

Subtask #5
20.9937903735 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 38 ms 824 KB Output is partially correct
2 Partially correct 38 ms 584 KB Output is partially correct
3 Partially correct 41 ms 856 KB Output is partially correct
4 Partially correct 36 ms 872 KB Output is partially correct

Subtask #6
17.4357887067 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 87 ms 1212 KB Output is partially correct
2 Partially correct 90 ms 1652 KB Output is partially correct
3 Partially correct 94 ms 1048 KB Output is partially correct
4 Partially correct 97 ms 1332 KB Output is partially correct
5 Partially correct 38 ms 824 KB Output is partially correct
6 Partially correct 38 ms 584 KB Output is partially correct
7 Partially correct 41 ms 856 KB Output is partially correct
8 Partially correct 36 ms 872 KB Output is partially correct
9 Partially correct 134 ms 1284 KB Output is partially correct
10 Partially correct 136 ms 1352 KB Output is partially correct
11 Partially correct 144 ms 1968 KB Output is partially correct
12 Partially correct 142 ms 1648 KB Output is partially correct