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
#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)
      |                      ~~^~~~~~~~~~~~~
# 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