oj.uz

Submission #1117410

# Submission time Handle Problem Language Result Execution time Memory
1117410 2024-11-23T14:02:13 Z Tenis0206 Nicelines (RMI20_nicelines) C++11
71.882 / 100
 139 ms 1760 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 + 7;
    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 2 ms 336 KB Output is correct

Subtask #2
0.0 / 13.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
14.9731402375 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 85 ms 1140 KB Output is partially correct
2 Partially correct 92 ms 1456 KB Output is partially correct
3 Partially correct 99 ms 1096 KB Output is partially correct
4 Partially correct 95 ms 1116 KB Output is partially correct

Subtask #5
21.0910814752 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 36 ms 532 KB Output is partially correct
2 Partially correct 35 ms 792 KB Output is partially correct
3 Partially correct 35 ms 608 KB Output is partially correct
4 Partially correct 35 ms 1096 KB Output is partially correct

Subtask #6
17.8178057937 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 85 ms 1140 KB Output is partially correct
2 Partially correct 92 ms 1456 KB Output is partially correct
3 Partially correct 99 ms 1096 KB Output is partially correct
4 Partially correct 95 ms 1116 KB Output is partially correct
5 Partially correct 36 ms 532 KB Output is partially correct
6 Partially correct 35 ms 792 KB Output is partially correct
7 Partially correct 35 ms 608 KB Output is partially correct
8 Partially correct 35 ms 1096 KB Output is partially correct
9 Partially correct 136 ms 1572 KB Output is partially correct
10 Partially correct 139 ms 1512 KB Output is partially correct
11 Partially correct 128 ms 1760 KB Output is partially correct
12 Partially correct 126 ms 1276 KB Output is partially correct