oj.uz

Submission #97477

# Submission time Handle Problem Language Result Execution time Memory
97477 2019-02-16T11:25:50 Z Alexa2001 Last supper (IOI12_supper) C++17
100 / 100
 117 ms 10752 KB 
#include "advisor.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

static int nxt[Nmax], last[Nmax], in[Nmax], c[Nmax], scoate[Nmax];
static priority_queue < pair<int,int> > heap;

void ComputeAdvice(int *C, int N, int K, int M)
{
    int i;

    for(i=0; i<N; ++i) last[i] = N+K;

    for(i=0; i<K; ++i) c[i] = i;
    for(; i<N+K; ++i) c[i] = C[i-K];

    for(i=N+K-1; i>=0; --i)
    {
        nxt[i] = last[c[i]];
        last[c[i]] = i;
    }

    for(i=0; i<K; ++i)
    {
        in[i] = 1;
        heap.push({ nxt[i], i });
    }

    for(; i<N+K; ++i)
    {
        if(in[c[i]])
        {
            heap.push({ nxt[i], i });
            continue;
        }

        assert(heap.size());

        int node = heap.top().second;
        heap.pop();

        in[c[node]] = 0;
        in[c[i]] = 1;
        scoate[node] = 1;

        heap.push({ nxt[i], i });
    }

    for(i=0; i<N+K; ++i) WriteAdvice(scoate[i]);
}

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

using namespace std;

const int Nmax = 1e5 + 5;
static int in[Nmax];

void Assist(unsigned char *A, int N, int K, int R)
{
    int i;
    vector<int> active;

    for(i=0; i<K; ++i)
    {
        if(A[i]) active.push_back(i);
        in[i] = 1;
    }

    for(i=0; i<N; ++i)
    {
        int x = GetRequest();
        if(in[x])
        {
            if(A[K+i]) active.push_back(x);
            continue;
        }

        assert(active.size());

        int y = active.back();
        active.pop_back();

        PutBack(y);
        in[y] = 0;

        in[x] = 1;
        if(A[K+i]) active.push_back(x);
    }

    assert(active.empty());
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 940 KB Output is correct
4 Correct 7 ms 1072 KB Output is correct
5 Correct 7 ms 1096 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 8 ms 1280 KB Output is correct
8 Correct 11 ms 1280 KB Output is correct
9 Correct 9 ms 1096 KB Output is correct
10 Correct 9 ms 1280 KB Output is correct
11 Correct 11 ms 1280 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1480 KB Output is correct
2 Correct 39 ms 5352 KB Output is correct
3 Correct 82 ms 10712 KB Output is correct
4 Correct 75 ms 8640 KB Output is correct
5 Correct 101 ms 8688 KB Output is correct
6 Correct 78 ms 9184 KB Output is correct
7 Correct 81 ms 10200 KB Output is correct
8 Correct 71 ms 9008 KB Output is correct
9 Correct 81 ms 8208 KB Output is correct
10 Correct 101 ms 10712 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7576 KB Output is correct
2 Correct 87 ms 10752 KB Output is correct
3 Correct 93 ms 10584 KB Output is correct
4 Correct 95 ms 10520 KB Output is correct
5 Correct 75 ms 10456 KB Output is correct
6 Correct 105 ms 10456 KB Output is correct
7 Correct 84 ms 10456 KB Output is correct
8 Correct 87 ms 9952 KB Output is correct
9 Correct 117 ms 10120 KB Output is correct
10 Correct 97 ms 10456 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1024 KB Output is correct
2 Correct 11 ms 1280 KB Output is correct
3 Correct 9 ms 1024 KB Output is correct
4 Correct 13 ms 1096 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 12 ms 1280 KB Output is correct
8 Correct 6 ms 1296 KB Output is correct
9 Correct 8 ms 1296 KB Output is correct
10 Correct 10 ms 1280 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 8920 KB Output is correct - 120000 bits used
2 Correct 102 ms 9176 KB Output is correct - 122000 bits used
3 Correct 81 ms 9176 KB Output is correct - 125000 bits used
4 Correct 110 ms 9472 KB Output is correct - 125000 bits used
5 Correct 88 ms 9432 KB Output is correct - 125000 bits used
6 Correct 98 ms 9432 KB Output is correct - 125000 bits used
7 Correct 90 ms 9432 KB Output is correct - 124828 bits used
8 Correct 108 ms 9408 KB Output is correct - 124910 bits used
9 Correct 91 ms 9176 KB Output is correct - 125000 bits used
10 Correct 83 ms 8928 KB Output is correct - 125000 bits used