Submission #398542

#	Time	Username	Problem	Language	Result	Execution time	Memory
398542		model_code	Nicelines (RMI20_nicelines)	C++17	100 / 100	10 ms	316 KiB

nicelines

/**
* user:  test
* fname: Test
* lname: Testulescu
* task:  NiceLines
* score: 100.0
* date:  2020-12-04 11:07:48.089342
*/
/** George Chichirim
  * Q = 4 * N + 2
  * Expected: 100 points
  */

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

using namespace std;

const long double EPS = 0.0001;

const int MaxVal = 20000;
const int MaxX = MaxVal * 3;
const int Rest1 = MaxVal + 1;
const int Rest2 = 2 * MaxVal - 1;

typedef pair<long double, long double> Point;

set<long long> solution;

struct Line {
    long double a, b;

    Line(long double a, long double b) : a(a), b(b) {}
    Line(long double x1, long double y1, long double x2, long double y2) {
        a = (y2 - y1) / (x2 - x1);
        b = y1 - a * x1;
    }

    bool isOn(long double x, long double y) {
        return abs(x * a + b - y) < EPS;
    }
};

Point intersectLines(const Line& line1, const Line& line2) {
    long double x = (line2.b - line1.b) / (line1.a - line2.a);
    long double y = line1.a * x + line1.b;
    return {x, y};
}

long long closestUp(long long y, long long targetRest) {
    long long r = (y % MaxX + MaxX) % MaxX;
    if (r <= targetRest) return y + targetRest - r;
    else return y + MaxX + targetRest - r;

}

long long closestDown(long long y, long long targetRest) {
    if ((y - targetRest) % MaxX == 0) return y;
    else return closestUp(y, targetRest) - MaxX;
}

void divide(Line lowLine, Line highLine) {
    auto point = intersectLines(lowLine, highLine);
    long long y = round(point.first);
    long long rest = (y % MaxX + MaxX) % MaxX;
    long long upY1, upY2, downY1, downY2;
    if (Rest1 < rest && rest < Rest2) {
        downY1 = closestDown(y, Rest1), downY2 = closestUp(y, Rest2);
        upY1 = downY1 + MaxX, upY2 = downY2 + MaxX;
    } else {
        upY1 = closestUp(y, Rest1), upY2 = closestUp(y, Rest2);
        downY1 = closestDown(y, Rest1), downY2 = closestDown(y, Rest2);
    }

    assert((downY1 % MaxX + Rest2) % MaxX == 0);
    assert((downY2 % MaxX + Rest1) % MaxX == 0);
    assert((upY1 % MaxX + Rest2) % MaxX == 0);
    assert((upY2 % MaxX + Rest1) % MaxX == 0);

    long double downVal2 = query(MaxX, downY2);
    if (lowLine.isOn(downY2, downVal2)) {
        long double upVal1 = query(MaxX, upY1);
        if (highLine.isOn(upY1, upVal1)) {
            solution.insert(y);
        } else {
            long double upVal2 = query(MaxX, upY2);
            Line upMidLine(upY1, upVal1, upY2, upVal2);
            divide(upMidLine, highLine);
        }
    } else {
        long double downVal1 = query(MaxX, downY1);
        Line downMidLine(downY1, downVal1, downY2, downVal2);
        divide(lowLine, downMidLine);
        divide(downMidLine, highLine);
    }
}

void solve(int subtask_id, int n) {
    long long lowY1 = -1LL * MaxX * MaxX - Rest2;
    long double lowVal1 = query(MaxX, lowY1);
    long long lowY2 = -1LL * MaxX * MaxX - Rest1;
    long double lowVal2 = query(MaxX, lowY2);
    Line lowLine(lowY1, lowVal1, lowY2, lowVal2);

    long long highY1 = 1LL * MaxX * MaxX + Rest1;
    long double highVal1 = query(MaxX, highY1);
    long long highY2 = 1LL * MaxX * MaxX + Rest2;
    long double highVal2 = query(MaxX, highY2);
    Line highLine(highY1, highVal1, highY2, highVal2);

    divide(lowLine, highLine);
    vector<int> aSol, bSol;
    assert(solution.size() == n);
    for (auto y : solution) {
        int a, b;
        b = y % MaxX;
        if (b < -MaxVal) b += MaxX;
        if (b > MaxVal) b -= MaxX;
        a = (y - b) / MaxX;
        aSol.push_back(a);
        bSol.push_back(b);
    }
    the_lines_are(aSol, bSol);
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from nicelines.cpp:14:
nicelines.cpp: In function 'void solve(int, int)':
nicelines.cpp:113:28: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |     assert(solution.size() == n);
      |            ~~~~~~~~~~~~~~~~^~~~

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