Submission #649771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
649771	2022-10-11T10:45:37 Z	boris_mihov	Santa Claus (RMI19_santa)	C++17	20 / 100	1000 ms	147416 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;

inline bool cmp(std::pair <int,bool> x, std::pair <int,bool> y)
{
    return x.first > y.first || (x.first == y.first && x.second < y.second);
}

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

    std::sort(left.begin(), left.end(), cmp);

    int cnt = 0;
    int lPtr = 0;
    int rPtr = 0;
    while (lPtr < used[allowed-1].size() || rPtr < left.size())
    {
        if (lPtr == used[allowed-1].size())
        {
            if (left[rPtr].second == 0) cnt++;
            else if (cnt >= 1) cnt--;
            rPtr++;
            continue;
        }

        if (rPtr == left.size())
        {
            return false;
        }

        if (cmp({used[allowed-1][lPtr], 0}, left[rPtr]))
        {
            cnt++;
            lPtr++;
        } else
        {
            if (left[rPtr].second == 0) cnt++;
            else if (cnt >= 1) cnt--;
            rPtr++;
        }
    }
    
    return cnt == 0;
}

int maxElvePos;
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);
        std::reverse(used[i].begin(), used[i].end());
    }

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

    maxElvePos = r;
    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:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     while (lPtr < used[allowed-1].size() || rPtr < left.size())
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
santa.cpp:54:50: 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 |     while (lPtr < used[allowed-1].size() || rPtr < left.size())
      |                                             ~~~~~^~~~~~~~~~~~~
santa.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (lPtr == used[allowed-1].size())
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
santa.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if (rPtr == left.size())
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Incorrect	11 ms	2692 KB	Output isn't correct
3	Correct	820 ms	3520 KB	Output is correct
4	Execution timed out	1087 ms	4280 KB	Time limit exceeded
5	Execution timed out	1090 ms	5204 KB	Time limit exceeded
6	Execution timed out	1090 ms	10708 KB	Time limit exceeded
7	Execution timed out	1004 ms	57184 KB	Time limit exceeded
8	Execution timed out	1095 ms	127700 KB	Time limit exceeded
9	Execution timed out	1101 ms	140396 KB	Time limit exceeded
10	Execution timed out	1095 ms	147416 KB	Time limit exceeded