Submission #1117393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117393		Tenis0206	Nicelines (RMI20_nicelines)	C++11	82.50 / 100	145 ms	512 KiB

nicelines

#include <bits/stdc++.h>
#include "nice_lines.h"

using namespace std;

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

vector<int> a, b;

long double my_query(long double A, long double B)
{
    long double rez = 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 (stderr)

nicelines.cpp: In function 'long double my_query(long double, long double)':
nicelines.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<a.size();i++)
      |                 ~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 14.1140029172 / 19
• Subtask 5: 20.7790789749 / 23
• Subtask 6: 16.6067722449 / 27