oj.uz

Submission #63017

# Submission time Handle Problem Language Result Execution time Memory
63017 2018-07-31T09:58:10 Z SpaimaCarpatilor Last supper (IOI12_supper) C++17
100 / 100
 140 ms 24872 KB 
#include "advisor.h"
#include<bits/stdc++.h>

using namespace std;

static int lst[100009], nxt[100009], realVal[200009];
static bool ap[100009], ans[200009];
static priority_queue < pair < int, int > > PQ;

void ComputeAdvice(int *C, int N, int K, int M)
{
    for (int i=0; i<N; i++)
        lst[i] = N + 1;
    for (int i=N - 1; i>=0; i--)
    {
        nxt[i] = lst[C[i]];
        lst[C[i]] = i;
    }
    for (int i=0; i<K; i++)
        PQ.push ({lst[i], i}),
        realVal[i] = lst[i], ap[i] = 1;
    for (int i=0; i<N; i++)
    {
        if (ap[C[i]] == 1)
        {
            PQ.push ({nxt[i], i + K});
            realVal[i + K] = nxt[i];
            continue;
        }
        pair < int, int > curr;
        int currC;
        while (1)
        {
            curr = PQ.top ();
            PQ.pop ();
            if (curr.second < K) currC = curr.second;
            else currC = C[curr.second - K];
            if (realVal[curr.second] == curr.first && ap[currC] == 1)
                break;
        }
        ap[currC] = 0, ans[curr.second] = 1;
        ap[C[i]] = 1, PQ.push ({nxt[i], i + K});
        realVal[i + K] = nxt[i];
    }
    for (int i=0; i<N + K; i++)
        WriteAdvice (ans[i]);
}

#include "assistant.h"
#include<bits/stdc++.h>

using namespace std;

static bool ap[100009], dispensable[100009];
static queue < int > canDispense;

void Assist(unsigned char *A, int N, int K, int R)
{
    for (int i=0; i<K; i++)
    {
        ap[i] = 1,
        dispensable[i] = A[i];
        if (dispensable[i])
            canDispense.push (i);
    }
    for (int i = 0; i < N; i++)
    {
        int req = GetRequest();
        if (ap[req])
        {
            if (A[K + i])
                dispensable[req] = 1, canDispense.push (req);
            continue;
        }
        assert (!canDispense.empty ());
        {
            int c = canDispense.front ();
            canDispense.pop ();
            ap[c] = 0;
            PutBack (c);
        }
        if (A[K + i])
            dispensable[req] = ap[req] = 1, canDispense.push (req);
        else
            ap[req] = 1;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 616 KB Output is correct
2 Correct 5 ms 1072 KB Output is correct
3 Correct 6 ms 1192 KB Output is correct
4 Correct 8 ms 1320 KB Output is correct
5 Correct 8 ms 1576 KB Output is correct
6 Correct 12 ms 1680 KB Output is correct
7 Correct 7 ms 1992 KB Output is correct
8 Correct 10 ms 1992 KB Output is correct
9 Correct 10 ms 2208 KB Output is correct
10 Correct 10 ms 2208 KB Output is correct
11 Correct 9 ms 2208 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2704 KB Output is correct
2 Correct 46 ms 5904 KB Output is correct
3 Correct 102 ms 10712 KB Output is correct
4 Correct 94 ms 10712 KB Output is correct
5 Correct 84 ms 11464 KB Output is correct
6 Correct 97 ms 13160 KB Output is correct
7 Correct 123 ms 15056 KB Output is correct
8 Correct 103 ms 15056 KB Output is correct
9 Correct 77 ms 15928 KB Output is correct
10 Correct 94 ms 18704 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 18704 KB Output is correct
2 Correct 111 ms 18704 KB Output is correct
3 Correct 112 ms 18752 KB Output is correct
4 Correct 140 ms 18752 KB Output is correct
5 Correct 83 ms 18864 KB Output is correct
6 Correct 93 ms 19736 KB Output is correct
7 Correct 100 ms 20824 KB Output is correct
8 Correct 102 ms 21536 KB Output is correct
9 Correct 111 ms 23496 KB Output is correct
10 Correct 89 ms 24344 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24344 KB Output is correct
2 Correct 10 ms 24344 KB Output is correct
3 Correct 9 ms 24344 KB Output is correct
4 Correct 11 ms 24344 KB Output is correct
5 Correct 10 ms 24344 KB Output is correct
6 Correct 10 ms 24344 KB Output is correct
7 Correct 8 ms 24344 KB Output is correct
8 Correct 10 ms 24344 KB Output is correct
9 Correct 10 ms 24344 KB Output is correct
10 Correct 10 ms 24344 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 24544 KB Output is correct - 120000 bits used
2 Correct 106 ms 24552 KB Output is correct - 122000 bits used
3 Correct 106 ms 24728 KB Output is correct - 125000 bits used
4 Correct 100 ms 24872 KB Output is correct - 125000 bits used
5 Correct 86 ms 24872 KB Output is correct - 125000 bits used
6 Correct 119 ms 24872 KB Output is correct - 125000 bits used
7 Correct 101 ms 24872 KB Output is correct - 124828 bits used
8 Correct 120 ms 24872 KB Output is correct - 124910 bits used
9 Correct 90 ms 24872 KB Output is correct - 125000 bits used
10 Correct 89 ms 24872 KB Output is correct - 125000 bits used