Submission #1067532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067532		andrei_iorgulescu	Aliens (IOI16_aliens)	C++14	100 / 100	636 ms	11136 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#warning That's not FB, that's my FB

using namespace std;

using ll = long long;
using ld = long double;

const ld eps = 0.00000001d;

int n, m;
vector<int> l, r;

bool cmp(pair<int,int> A, pair<int,int> B)
{
    if (A.first != B.first)
        return A.first < B.first;
    return A.second > B.second;
}

void norma_intvs()
{
    vector<pair<int,int>> vp;
    for (int i = 0; i < l.size(); i++)
        vp.push_back({l[i], r[i]});
    sort(vp.begin(), vp.end(), cmp);
    l.clear();
    r.clear();
    int rmax = -1;
    for (auto it : vp)
    {
        if (it.second > rmax)
        {
            rmax = it.second;
            l.push_back(it.first);
            r.push_back(it.second);
        }
    }
}

struct ura
{
    ld val;
    int cate;
};

ura dp[200005];

struct dreapta
{
    ld offset, panta;
    int idx;
};

ld inters(dreapta d1, dreapta d2)
{
    return (d2.offset - d1.offset) / (d1.panta - d2.panta);
}

deque<dreapta> dq;

void baga(dreapta d)
{
    dq.push_back(d);
    while (dq.size() >= 3)
    {
        dreapta d1 = dq.back();
        dq.pop_back();
        dreapta d2 = dq.back();
        dq.pop_back();
        dreapta d3 = dq.back();
        dq.pop_back();
        if (inters(d2, d3) >= inters(d1, d2))
        {
            dq.push_back(d3);
            dq.push_back(d1);
        }
        else
        {
            dq.push_back(d3);
            dq.push_back(d2);
            dq.push_back(d1);
            break;
        }
    }
}

dreapta query(ld x)
{
    while (dq.size() >= 2)
    {
        dreapta d1 = dq.front();
        dq.pop_front();
        dreapta d2 = dq.front();
        dq.pop_front();
        if (inters(d1, d2) <= x)
            dq.push_front(d2);
        else
        {
            dq.push_front(d2);
            dq.push_front(d1);
            break;
        }
    }
    return dq.front();
}

void solve(ld cost)
{
    dp[0].val = dp[0].cate = 0;
    dq.clear();
    for (int i = 1; i <= n; i++)
    {
        dreapta cur;
        cur.idx = i;
        cur.offset = dp[i - 1].val + (ld)l[i] * (ld)l[i];
        if (i != 1 and l[i] <= r[i - 1])
            cur.offset -= (ld)(r[i - 1] - l[i] + 1) * (ld)(r[i - 1] - l[i] + 1);
        cur.panta = -l[i];
        baga(cur);
        dreapta sol = query(2 * r[i] + 2);
        dp[i].cate = 1 + dp[sol.idx - 1].cate;
        dp[i].val = cost + (ld)(r[i] + 1) * (ld)(r[i] + 1) + sol.offset + (ld)(2 * r[i] + 2) * sol.panta;
    }
}

ll take_photos(int N, int M, int k, vector<int> R, vector<int> C)
{
    n = N, m = M;
    for (int i = 0; i < n; i++)
    {
        l.push_back(min(R[i],C[i]));
        r.push_back(max(R[i],C[i]));
    }
    norma_intvs();
    n = l.size();
    vector<int> newl = {0};
    for (auto it : l)
        newl.push_back(it);
    l = newl;
    vector<int> newr = {0};
    for (auto it : r)
        newr.push_back(it);
    r = newr;
    ld st = (ll)1e6 * (ll)1e6;
    ld pas = 1ll << 39;
    while (pas >= eps)
    {
        if (st - pas >= 0)
        {
            solve(st - pas);
            if (dp[n].cate <= k)
                st -= pas;
        }
        pas /= 2.0d;
    }
    solve(st);
    ld ans = dp[n].val - st * (ld)k;
    if (ans - (ll)ans <= 0.5d)
        return (ll)ans;
    return (ll)ans + 1;
}

Compilation message (stderr)

aliens.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
aliens.cpp: In function 'void norma_intvs()':
aliens.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~

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