oj.uz

Submission #1117409

# Submission time Handle Problem Language Result Execution time Memory
1117409 2024-11-23T14:01:38 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
77.8803 / 100
 128 ms 1960 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 + 1;
    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

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

Subtask #3
0.0 / 7.0

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

Subtask #4
14.9759116478 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 87 ms 1672 KB Output is partially correct
2 Partially correct 89 ms 812 KB Output is partially correct
3 Partially correct 91 ms 968 KB Output is partially correct
4 Partially correct 87 ms 1216 KB Output is partially correct

Subtask #5
21.0944363403 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 34 ms 584 KB Output is partially correct
2 Partially correct 33 ms 840 KB Output is partially correct
3 Partially correct 42 ms 584 KB Output is partially correct
4 Partially correct 33 ms 584 KB Output is partially correct

Subtask #6
17.8099291512 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 87 ms 1672 KB Output is partially correct
2 Partially correct 89 ms 812 KB Output is partially correct
3 Partially correct 91 ms 968 KB Output is partially correct
4 Partially correct 87 ms 1216 KB Output is partially correct
5 Partially correct 34 ms 584 KB Output is partially correct
6 Partially correct 33 ms 840 KB Output is partially correct
7 Partially correct 42 ms 584 KB Output is partially correct
8 Partially correct 33 ms 584 KB Output is partially correct
9 Partially correct 122 ms 1412 KB Output is partially correct
10 Partially correct 128 ms 1540 KB Output is partially correct
11 Partially correct 127 ms 1632 KB Output is partially correct
12 Partially correct 123 ms 1960 KB Output is partially correct