Submission #1291444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291444		sahtehesap123	Aliens (IOI16_aliens)	C++20	60 / 100	73 ms	3112 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#define ll long long
using namespace std;

constexpr static ll INF = 1e15;

vector<array<int, 2>> get_cells(const vector<int>& r, const vector<int>& c) {
        const int n = r.size();
        vector<array<int, 2>> cells;
        for (int i = 0; i < n; i++) {
                cells.push_back({min(r[i], c[i]), -max(r[i], c[i])});
        }
        sort(cells.begin(), cells.end());
        vector<array<int, 2>> final_cells;
        int lastc = -1;
        for (auto [r, c] : cells) {
                if (-c <= lastc)
                        continue;
                lastc = -c;
                final_cells.push_back({r, -c});
        }
        return final_cells;
}

ll calculate_cost(array<ll, 3> line, ll c, ll lambda) {
        return line[0] + line[1] * c + c * c + lambda;
}


bool beating_intercept(const deque<array<ll, 3>>& d, ll y2, ll s2) {
        if (d.size() == 0) return false;
        if (y2 < d[0][0]) return true;
        if (d.size() == 1) return false;
        auto [ y1, s1, _ ] = d.back();
        auto [ y0, s0, __ ] = d[d.size()-2];
        assert(y0 <= y1 && y1 <= y2);
        assert(s2 <= s1 && s1 <= s0);
        return (y1 - y2) * (s1 - s0) <= (y0 - y1) * (s2 - s1);
}

array<ll, 2> get_count_val(const std::vector<array<int, 2>>& cells, ll lambda) {
        const int n = cells.size();
        deque<array<ll, 3>> dp; // (Initial point, slope, number of attempts)
        ll initial_y_intercept = static_cast<ll>(cells[0][0] - 1) * (cells[0][0] - 1);
        ll initial_slope = - 2 * (cells[0][0] - 1);
        dp.push_back({initial_y_intercept, initial_slope, 0});
        for (int i = 1; i <= n; i++) {
                int c = cells[i-1][1];
                while (dp.size() > 1 && calculate_cost(dp[0], c, lambda) > calculate_cost(dp[1], c, lambda)) dp.pop_front();
                ll cost = calculate_cost(dp[0], c, lambda);
                int steps = dp[0][2] + 1;
                if (i < n) {
                        ll y_intercept = cost + static_cast<ll>(cells[i][0] - 1) * (cells[i][0] - 1) - max<ll>(0, c - cells[i][0] + 1) * max<ll>(0, c - cells[i][0] + 1);
                        ll slope = -2 * (cells[i][0] - 1);
                        while (beating_intercept(dp, y_intercept, slope)) dp.pop_back();
                        dp.push_back({y_intercept, slope, steps});
                }
                else {
                        return { cost - lambda * steps, steps };
                }
        }
        assert(false);
}

long long take_photos(int n, int m, int k, std::vector<int> rows, std::vector<int> columns) {
        assert(n*k <= 1e8);
        vector<array<int, 2>> cells = get_cells(rows, columns);
        ll l = 0, r = 1e12;
        while (r - l > 1) {
                ll m = (r+l) / 2;
                //cout << l << " " << r << " " << m << " " << get_count_val(cells, m)[0] << " " << get_count_val(cells, m)[1] << "\n";
                if (get_count_val(cells, m)[1] < static_cast<ll>(k))
                        r = m;
                else
                        l = m;
        }
        auto [ lc, ls ] = get_count_val(cells, l);
        auto [ rc, rs ] = get_count_val(cells, r);
        if (rs == ls)
                return lc;
        ll res = (rc - lc) * (k - ls) / (rs - ls) + lc;
        //cout << steps << "\n";
        assert(ls >= k && k >= rs);
        return res;
}

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: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 40