Submission #617290

#	Time	Username	Problem	Language	Result	Execution time	Memory
617290		Drew_	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	169 ms	22832 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
#define size(x) (int)x.size()

using ll = long long;
using ii = pair<int, int>;

const ll inf = 1e18 + 69;


namespace sub1
{
    ll solve(vector<int> s,vector<int> t)
    {
        int n = size(s);
        vector<ii> v(n);
        for (int i = 0; i < n; ++i)
            v[i] = {s[i], t[i]};
        sort(v.begin(), v.end());

        ll mn = inf;
        do
        {
            ll ctr = 0;
            for (int i = 0, cur = 1; i < n; ++i)
            {
                ctr += max(0, cur - v[i].f1);
                cur = v[i].s2;
            }
            mn = min(mn, ctr);

            if (ctr == 8)
            {
                for (auto [l, r] : v)
                    cout << l << " " << r << " -- ";
                cout << '\n';
                for (auto [l, r] : v) if (l < r)
                    cout << l << " " << r << " __ ";
                cout << '\n';
                for (auto [l, r] : v) if (l >= r)
                    cout << l << " " << r << " -- ";
                cout << "\n\n";
            }

        } while (next_permutation(v.begin(), v.end()));
        return mn;
    }
}

namespace sub2
{
    ll solve(vector<int> s, vector<int> t)
    {
        int N = size(s);
        vector<vector<ll>> dp(N, vector<ll>(1 << N, inf));
        const auto rc = [&](const auto &self, int id, int mask) -> ll
        {
            if (mask == (1 << N) - 1)
                return 0;
            if (dp[id][mask] != inf)
                return dp[id][mask];
            for (int i = 0; i < N; ++i) if (~mask >> i & 1)
                dp[id][mask] = min(dp[id][mask], max(0, t[id] - s[i]) + self(self, i, mask | (1 << i)));
            return dp[id][mask];
        };

        ll res = inf;
        for (int i = 0; i < N; ++i)
            res = min(res, rc(rc, i, 1 << i));
        return res;
    }
}  

namespace full
{
    ll solve(vector<int> s, vector<int> t)
    {
        vector<int> zip = { 1 };
        for (int x : s)
            zip.pb(x);
        for (int x : t)
            zip.pb(x);

        sort(zip.begin(), zip.end());
        zip.resize(unique(zip.begin(), zip.end()) - zip.begin());
        for (int &x : s)
            x = (int)(lower_bound(zip.begin(), zip.end(), x) - zip.begin());
        for (int &x : t)
            x = (int)(lower_bound(zip.begin(), zip.end(), x) - zip.begin());


        int n = size(s);
        vector<ii> v1, v2;
        for (int i = 0; i < n; ++i)
        {
            if (s[i] < t[i]) v1.pb({s[i], t[i]});
            else v2.pb({s[i], t[i]});
        }

        sort(v1.begin(), v1.end());
        sort(v2.begin(), v2.end(), [](ii &x, ii &y){
            return x.s2 < y.s2;
        });

        vector<ll> pfx(size(zip), 0);

        int mn = 1e9;
        for (int i = 0, j = 0; i+1 < size(v1); ++i)
        {
            if (v1[i].s2 > v1[i+1].f1)
            {
                pfx[v1[i+1].f1]++;
                pfx[v1[i].s2]--;
                mn = min(mn, v1[i+1].f1);
            }
        }

        for (auto [l, r] : v2)
        {
            if (l < mn)
            {
                pfx[l]++, pfx[mn]--;
                mn = l;
            }
            pfx[r]--, pfx[l]++;
        }
        for (int i = 1; i < size(pfx); ++i)
            pfx[i] += pfx[i-1];

        ll res = 0;
        for (int i = 0; i+1 < size(pfx); ++i)
            res += 1ll * max(0ll, pfx[i]) * (zip[i+1] - zip[i]);

        return res;
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    // cerr << "sub1 " << sub1 :: solve(s, t) << '\n';
    // cerr << "sub3 " << sub3 :: solve(s, t) << '\n';
    return full :: solve(s, t);
}

// int main() {
//     mt19937 RNG(69);
//     const auto randint = [&](int l, int r) -> int
//     {
//         return uniform_int_distribution<int>(l, r)(RNG);
//     };

//     for (int rep = 0; rep < 100; ++rep)
//     {
//         cerr << "rep " << rep << '\n';

//         int n = 7;
//         vector<int> s(n), t(n);
//         for (int i = 0; i < n; ++i)
//             s[i] = randint(1, 10), t[i] = randint(1, 10);

//         if (sub2 :: solve(s, t))
//         {
//             cout << n << '\n';
//             for (int i = 0; i < n; ++i)
//                 cout << s[i] << " " << t[i] << '\n';
//             return 0;
//         }
//     }
//     return 0;
// }

Compilation message (stderr)

railroad.cpp: In function 'll full::solve(std::vector<int>, std::vector<int>)':
railroad.cpp:114:25: warning: unused variable 'j' [-Wunused-variable]
  114 |         for (int i = 0, j = 0; i+1 < size(v1); ++i)
      |                         ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36