Submission #649780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
649780	2022-10-11T10:52:33 Z	boris_mihov	Santa Claus (RMI19_santa)	C++17	30 / 100	1000 ms	153204 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 (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(), cmp);
 
    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;
int minElveIdx;
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 = minElveIdx - 1, r = n + 1, mid;
    if (check(minElveIdx, 1)) r = minElveIdx;
    else l = minElveIdx;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (!check(mid, 1)) l = mid;
        else r = mid;  
    }

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

        while (ptr + 1 <= i && check(i, ptr + 1)) ptr++;
        if (l == 0) std::cout << -1 << ' ';
        else std::cout << 2*x[i] - x[ptr] << ' ';
    }

    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];
            minElveIdx = 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:57: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]
   57 |     for (int i = 0 ; i < left.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	4 ms	2736 KB	Output is correct
3	Correct	254 ms	3376 KB	Output is correct
4	Execution timed out	1041 ms	4412 KB	Time limit exceeded
5	Execution timed out	1096 ms	9292 KB	Time limit exceeded
6	Execution timed out	1097 ms	10316 KB	Time limit exceeded
7	Execution timed out	1102 ms	57040 KB	Time limit exceeded
8	Execution timed out	1097 ms	132752 KB	Time limit exceeded
9	Execution timed out	1096 ms	142980 KB	Time limit exceeded
10	Execution timed out	1102 ms	153204 KB	Time limit exceeded