Submission #649761

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
649761	2022-10-11T10:33:32 Z	boris_mihov	Santa Claus (RMI19_santa)	C++17	30 / 100	1000 ms	155788 KB

santa

#include <algorithm>
#include <iostream>
#include <tgmath.h>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <set>

typedef long long llong; 
const int MAXN = 100000 + 10;
const int MOD  = 1e9 + 7;
const int INF  = 1e9;

struct House
{
    int x, h, v;
    inline friend bool operator < (const House &a, const House &b)
    {
        return a.x < b.x || (a.x == b.x && a.h < b.h) || (a.x == b.x && a.h == b.h && a.v < b.v);
    }
} houses[MAXN];

int n, t;
int x[MAXN];
int h[MAXN];
int v[MAXN];
bool gotPresent[MAXN];

std::multiset <int> s;
std::multiset <int> toGive;
std::vector <int> used[MAXN];
std::vector <std::pair <int,bool>> left;
bool check(int idx, int allowed)
{
    left.clear();
    for (const int &i : used[allowed-1]) 
    {
        left.emplace_back(i, 0);
    }

    for (int i = allowed ; i <= idx ; ++i)
    {
        left.emplace_back(v[i], h[i]);
    }

    std::sort(left.begin(), left.end(), [&](auto x, auto y)
    {
        return x.first > y.first || (x.first == y.first && x.second < y.second);
    });

    int cnt = 0;
    for (int i = 0 ; i < left.size() ; ++i)
    {
        if (left[i].second == 0) cnt++;
        else if (cnt >= 1) cnt--;
    }
    
    return cnt == 0;
}

int maxElvePos = 0;
void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        if (h[i] == 0) toGive.insert(v[i]);
        else
        {
            auto it = toGive.lower_bound(v[i]);
            if (it != toGive.end()) toGive.erase(it);
        }

        used[i].clear();
        used[i].reserve(toGive.size());
        for (const int &j : toGive) used[i].push_back(j);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (x[i] < maxElvePos)
        {
            std::cout << -1 << ' ';
            continue;
        }

        int l = 0, r = i + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (check(i, mid)) l = mid;
            else r = mid;
        }

        if (l == 0) std::cout << -1 << ' ';
        else std::cout << 2*x[i] - x[l] << ' ';
    }

    std::cout << '\n';
}

void read()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].x;
    for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].h;
    for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].v;
    std::sort(houses + 1, houses + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        x[i] = houses[i].x;
        h[i] = houses[i].h;
        v[i] = houses[i].v;
        if (h[i] == 0) maxElvePos = x[i];
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    std::cin >> t;
    while (t--)
    {
        read();
        solve();
    }

    return 0;
}

Compilation message

santa.cpp: In function 'bool check(int, int)':
santa.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0 ; i < left.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Correct	6 ms	2644 KB	Output is correct
3	Correct	584 ms	3368 KB	Output is correct
4	Execution timed out	1044 ms	3816 KB	Time limit exceeded
5	Execution timed out	1092 ms	4968 KB	Time limit exceeded
6	Execution timed out	1058 ms	10324 KB	Time limit exceeded
7	Execution timed out	1081 ms	57556 KB	Time limit exceeded
8	Execution timed out	1092 ms	129096 KB	Time limit exceeded
9	Execution timed out	1070 ms	142848 KB	Time limit exceeded
10	Execution timed out	1089 ms	155788 KB	Time limit exceeded