Submission #287040

# Submission time Handle Problem Language Result Execution time Memory
287040 2020-08-31T09:52:43 Z andreiomd Santa Claus (RMI19_santa) C++11
0 / 100
1000 ms 384 KB
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int NMAX = 96068 + 5;

int T;
int N, X[NMAX], V[NMAX];
bool H[NMAX];

int the_last_elf;

int ans[NMAX];

multiset < int > S;

namespace InParser
{
static const int BSIZE = (1 << 16);

static int pos = (BSIZE - 1);
static char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        int n = fread(buff, 1, BSIZE, stdin);

        if(n != BSIZE)
            for(int i = n; i < BSIZE; ++i)
                buff[i] = 0;
    }

    return buff[pos];
}

inline int Int ()
{
    int ans = 0;

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
        {
            ans = (int)(Ch - '0');

            break;
        }
    }

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
            ans = ans * 10 + (int)(Ch - '0');
        else
            break;
    }

    return ans;
}
};

static inline void Read ()
{
    N = InParser :: Int();

    for(int i = 1; i <= N; ++i)
        X[i] = InParser :: Int();

    the_last_elf = 0;

    for(int i = 1; i <= N; ++i)
    {
        H[i] = InParser :: Int();

        if(!H[i])
            the_last_elf = i;
    }

    for(int i = 1; i < the_last_elf; ++i)
        ans[i] = -1;

    for(int i = 1; i <= N; ++i)
        V[i] = InParser :: Int();

    return;
}

static inline bool Check (int Destination, int Middle)
{
    S.clear();

    for(int i = 1; i < Middle; ++i)
        if(H[i] == 0)
            S.insert(V[i]);
        else
        {
            auto it = S.lower_bound(V[i]);

            if(it != S.end())
                S.erase(it);
        }

    for(int i = Middle; i <= Destination; ++i)
        if(H[i] == 0)
            S.insert(V[i]);

    for(int i = Middle; i <= Destination; ++i)
        if(H[i] == 1)
        {
            auto it = S.lower_bound(V[i]);

            if(it != S.end())
                S.erase(it);
        }

    return (bool)(S.empty());
}

static inline int Go (int pos)
{
    int Left = 1, Right = pos, ans = 0;

    while(Left <= Right)
    {
        int Mid = (Left + Right) >> 1;

        if(Check(pos, Mid))
            ans = Mid, Left = Mid + 1;
        else
            Right = Mid - 1;
    }

    if(ans == 0)
        return -1;

    return ((X[pos] << 1) - X[ans]);
}

static inline void Solve ()
{
    for(int i = the_last_elf; i <= N; ++i)
        ans[i] = Go(i);

    return;
}

static inline void Write ()
{
    for(int i = 1; i <= N; ++i)
    {
        printf("%d", ans[i]);

        if(i != N)
            printf(" ");
    }

    printf("\n");

    return;
}

static inline void TestCase ()
{
    Read();

    Solve();

    Write();

    return;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("santaclaus.in", "r", stdin);
    freopen("santaclaus.out", "w", stdout);

    T = InParser :: Int();

    while(T--)
        TestCase();

    return 0;
}

Compilation message

santa.cpp: In function 'int main()':
santa.cpp:190:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  190 |     freopen("santaclaus.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
santa.cpp:191:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  191 |     freopen("santaclaus.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 384 KB Time limit exceeded
2 Execution timed out 1090 ms 384 KB Time limit exceeded
3 Execution timed out 1092 ms 384 KB Time limit exceeded
4 Execution timed out 1093 ms 384 KB Time limit exceeded
5 Execution timed out 1097 ms 384 KB Time limit exceeded
6 Execution timed out 1090 ms 384 KB Time limit exceeded
7 Execution timed out 1087 ms 384 KB Time limit exceeded
8 Execution timed out 1083 ms 384 KB Time limit exceeded
9 Execution timed out 1083 ms 384 KB Time limit exceeded
10 Execution timed out 1091 ms 384 KB Time limit exceeded