oj.uz

Submission #647023

# Submission time Handle Problem Language Result Execution time Memory
647023 2022-10-01T12:14:16 Z danikoynov Nicelines (RMI20_nicelines) C++14
71.5607 / 100
 132 ms 356 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 = 1e4 + 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 = - 2 * maxcor * 2 * maxcor, rf = 2 * maxcor * 2 * 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 2 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 3 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 208 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 5 ms 208 KB Output is correct
2 Correct 4 ms 208 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct

Subtask #4
10.1938424674 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 106 ms 296 KB Output is partially correct
2 Partially correct 104 ms 208 KB Output is partially correct
3 Partially correct 90 ms 304 KB Output is partially correct
4 Partially correct 105 ms 296 KB Output is partially correct

Subtask #5
19.1083559067 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 24 ms 356 KB Output is partially correct
2 Partially correct 47 ms 208 KB Output is partially correct
3 Partially correct 29 ms 208 KB Output is partially correct
4 Partially correct 35 ms 208 KB Output is partially correct

Subtask #6
11.2585330269 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 106 ms 296 KB Output is partially correct
2 Partially correct 104 ms 208 KB Output is partially correct
3 Partially correct 90 ms 304 KB Output is partially correct
4 Partially correct 105 ms 296 KB Output is partially correct
5 Partially correct 24 ms 356 KB Output is partially correct
6 Partially correct 47 ms 208 KB Output is partially correct
7 Partially correct 29 ms 208 KB Output is partially correct
8 Partially correct 35 ms 208 KB Output is partially correct
9 Partially correct 116 ms 328 KB Output is partially correct
10 Partially correct 127 ms 336 KB Output is partially correct
11 Partially correct 132 ms 208 KB Output is partially correct
12 Partially correct 116 ms 292 KB Output is partially correct