Submission #1189723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189723		ericl23302	Aliens (IOI16_aliens)	C++20	12 / 100	1 ms	328 KiB

aliens

#include "aliens.h"

#include <iostream>
#include <algorithm>
#include <utility>
#include <climits>
#include <complex>
using namespace std;
using ll = long long;

typedef complex<ll> point;
#define x real
#define y imag

ll sq(ll a) {
    return a * a;
}
ll sq(int a) {
    return (ll)(a) * a;
}

// ll getArea(pair<ll, ll> a) {
//     return sq(a.second - a.first + 1);
// }
// ll getArea(ll a, ll b) {
//     return sq(b - a + 1);
// }

ll positiveArea(ll a, ll b) {
    ll sideLength = b - a + 1;
    return (sideLength > 0 ? sq(sideLength) : 0);
}

ll dot(point a, point b) {
    return ((conj(a) * b).x());
}

ll cross(point a, point b) {
    return ((conj(a) * b).y());
}

vector<point> hull, vec;
vector<ll> countHull;

void addLine(ll m, ll c, ll count) {
    point newLine({m, c});
    while (!vec.empty() && (dot(vec.back(), newLine - hull.back()) < 0)) {
        vec.pop_back();
        hull.pop_back();
        countHull.pop_back();
    }
    if (!hull.empty()) vec.push_back(point({0, 1}) * (newLine - hull.back()));
    countHull.push_back(count);
    hull.push_back(newLine);
}

pair<ll, ll> query(ll ri) {
    point toFind({ri, 1});
    ll idx = lower_bound(vec.begin(), vec.end(), toFind, [](point a, point b) {return (cross(a, b) > 0);}) - vec.begin();
    return {dot(toFind, hull[idx]), countHull[idx]};
}

ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    vector<pair<ll, ll>> oriPoints, points;
    for (ll i = 0; i < n; ++i) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        oriPoints.emplace_back(r[i], c[i]);
    }
    sort(oriPoints.begin(), oriPoints.end());
    
    pair<ll, ll> cur = oriPoints[0];
    for (ll i = 1; i < n; ++i) {
        if (oriPoints[i].first == cur.first) cur.second = max(oriPoints[i].second, cur.second);
        else if (cur.second < oriPoints[i].second) {
            if (cur.first != -1) points.emplace_back(cur);
            cur = oriPoints[i];
        }
    }
    points.emplace_back(cur);
    int newN = points.size();


    auto check = [&] (ll cost, ll &res) {
        hull.clear(); vec.clear(); countHull.clear();
        vector<ll> dp(newN + 1, 0), counts(newN + 1, 0);
        for (int i = 1; i <= newN; ++i) {
            ll m = 2 * (points[i - 1].first - 1), c = sq(points[i - 1].first - 1) + dp[i - 1] + (i > 1 ? positiveArea(points[i - 1].first, points[i - 2].second) : 0);
            addLine(m, c, counts[i - 1]);
            auto cur = query(-points[i - 1].second);
            dp[i] = cur.first + cost + sq(points[i - 1].second);
            counts[i] = cur.second + 1;
        }
        res = dp[newN];
        return (counts[newN] <= k);
    };

    ll low = 0, high = sq(m), res = LLONG_MAX / 2;
    while (low < high) {
        ll mid = (low + high) / 2;
        if (check(mid, res)) high = mid;
        else low = mid + 1;
    }
    check(low, res);
    
    return (res - k * low);
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 12 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40