oj.uz

Submission #647022

# Submission time Handle Problem Language Result Execution time Memory
647022 2022-10-01T12:11:59 Z danikoynov Nicelines (RMI20_nicelines) C++14
69.9457 / 100
 135 ms 308 KB 
/**
 ____ ____ ____ ____ ____ ____
||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

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.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 300 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct

Subtask #4
9.6187747456 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 78 ms 292 KB Output is partially correct
2 Partially correct 105 ms 292 KB Output is partially correct
3 Partially correct 111 ms 216 KB Output is partially correct
4 Partially correct 107 ms 208 KB Output is partially correct

Subtask #5
18.9171285684 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 32 ms 300 KB Output is partially correct
2 Partially correct 42 ms 208 KB Output is partially correct
3 Partially correct 26 ms 300 KB Output is partially correct
4 Partially correct 34 ms 296 KB Output is partially correct

Subtask #6
10.4098249629 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 78 ms 292 KB Output is partially correct
2 Partially correct 105 ms 292 KB Output is partially correct
3 Partially correct 111 ms 216 KB Output is partially correct
4 Partially correct 107 ms 208 KB Output is partially correct
5 Partially correct 32 ms 300 KB Output is partially correct
6 Partially correct 42 ms 208 KB Output is partially correct
7 Partially correct 26 ms 300 KB Output is partially correct
8 Partially correct 34 ms 296 KB Output is partially correct
9 Partially correct 120 ms 308 KB Output is partially correct
10 Partially correct 130 ms 304 KB Output is partially correct
11 Partially correct 120 ms 296 KB Output is partially correct
12 Partially correct 135 ms 292 KB Output is partially correct