Submission #1117434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117434		Tenis0206	Nicelines (RMI20_nicelines)	C++11	88.68 / 100	108 ms	1772 KiB

nicelines

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

using namespace std;

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

vector<int> a, b;

map<pair<long double, long double>, bool> sel;
map<pair<long double, long double>, long double> rez_query;

long double my_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}];
}

int aprox(long double val)
{
    return (int)(val + 0.5);
}

void divide(long long st, long long dr, long long A)
{
    if(st == dr)
    {
        long long B = st;
        if(B == 0)
        {
            a.push_back(0);
            b.push_back(B);
            return;
        }
        long double val_cos = 0.5 * (my_query(A, st + 1) - 2 * my_query(A, st) + my_query(A, st - 1));
        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);
        return;
    }
    long long mij = (st + dr) >> 1;
    long double dif_dr = my_query(A, dr + 1) - my_query(A, dr);
    long double dif_mij = my_query(A, mij + 1) - my_query(A, mij);
    long double dif_st = my_query(A, st) - my_query(A, st - 1);
    if(abs(dif_mij - dif_st) > eps)
    {
        divide(st, mij, A);
    }
    if(abs(dif_dr - dif_mij) > eps)
    {
        divide(mij + 1, dr, A);
    }
}

void solve(int subtask_id, int n)
{
    if(subtask_id == 4)
    {
        cmax = 500;
    }
    long long A = cmax + 9;
    long long B = (A + 1) * cmax + 1;
    divide(-(A + 1) * cmax - 1, B, A);
    the_lines_are(a, b);
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 16.3380600126 / 19
• Subtask 5: 21.4752135855 / 23
• Subtask 6: 19.869670764 / 27