Submission #647022

#	Time	Username	Problem	Language	Result	Execution time	Memory
647022		danikoynov	Nicelines (RMI20_nicelines)	C++14	69.95 / 100	135 ms	308 KiB

nicelines

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'
#include "nice_lines.h"
using namespace std;
typedef long long ll;

int maxcor = 2e4 + 10;
const long double eps = 1e-9;
vector < long long > cur;
long long x;

bool process(long long lf, long long rf, long double d1, long double d2)
{
    if (rf - lf <= 1)
        return false;


    ///cout << lf << " :: " << rf << endl;
    long long mid = (lf + rf) / 2;
    long double md = query(x, mid);

    long double sum = (long double)(rf - lf) / (long double)(mid - lf) * (md - d1);
     ///cout << lf << " " << rf << " " << mid << " " << d1 << " " << md << " " << d2 << " " << sum << endl;
    if (abs(sum - (d2 - d1)) < eps)
    {
        ///cout << "here" << endl;
        return false;
    }

    bool tf1 = process(lf, (mid), d1, md);
    bool tf2 = process((mid), rf, md, d2);

    /**if (rf - lf < 100)
    {
        if (!tf1 && !tf2)
            cur.push_back((round)(mid));
    }
    else*/
    if ((query(x, mid - 1) - md) - (md - query(x, mid + 1)) > eps)
        cur.push_back((round)(mid));


    return max(tf1, tf2);
}

void solve(int subtask_id, int N)
{

    ///cout << (ceil)(2.0) << endl;
    cur.clear();
    x = maxcor * 2;
    long long lf = -maxcor * maxcor, rf = maxcor * maxcor;
    process(lf, rf, query(x, lf), query(x, rf));
    vector < long long > it1 = cur;

    /**cur.clear();
    x = maxcor * 2 + 1;
        process(lf, rf, query(x, lf), query(x, rf));
    vector < long long > it2 = cur;*/

    sort(it1.begin(), it1.end());
    ///sort(it2.begin(), it2.end());

    ///cout << it1.size() << " " << it2.size() << endl;
    vector < int > a, b;
    for (int i = 0; i < it1.size(); i ++)
    {
        ///cout << it1[i] << " " << it2[i] << endl;
        for (int pa = -1e4; pa <= 1e4; pa ++)
        {
            ll wd = (ll)(pa * x);
            ll lf = (round)(it1[i]) - wd;
            if (lf >= -1e4 && lf <= 1e4)
            {
                a.push_back(pa);
                b.push_back(lf);
            }
        }
        ///a.push_back((round)(it2[i] - it1[i]));
        ///b.push_back((round)(it2[i] - x * (it2[i] - it1[i])));
    }

    the_lines_are(a, b);


}

Compilation message (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 9.618774745600001 / 19
• Subtask 5: 18.9171285684 / 23
• Subtask 6: 10.4098249629 / 27