oj.uz

Submission #502240

# Submission time Handle Problem Language Result Execution time Memory
502240 2022-01-05T15:16:54 Z blue Last supper (IOI12_supper) C++17
100 / 100
 172 ms 8680 KB 
#include "advisor.h"
#include <deque>
#include <vector>
#include <set>
#include <iostream>
using namespace std;

using vi = vector<int>;

void ComputeAdvice(int *C, int N, int K, int M)
{
    vi curr(N, N);
    vi nxt(N, 0);
    for(int i = N-1; i >= 0; i--)
    {
        nxt[i] = curr[C[i]];
        curr[C[i]] = i;
    }

    set<pair<int, int> > scaffold;
    for(int c = 0; c < K; c++) scaffold.insert({curr[c], c});



    vi removed(N+K, 1);

    vi prv(N, -1);
    for(int c = 0; c < K; c++) prv[c] = c;

    for(int i = 0; i < N; i++)
    {
        if(scaffold.find({curr[C[i]], C[i]}) != scaffold.end())
        {
            scaffold.erase({curr[C[i]], C[i]});

            curr[C[i]] = nxt[curr[C[i]]];
            scaffold.insert({curr[C[i]], C[i]});

            // if(prv[C])
            removed[prv[C[i]]] = 0;
        }
        else
        {
            int z = scaffold.rbegin()->second;
            scaffold.erase({curr[z], z});

            curr[C[i]] = nxt[curr[C[i]]];
            scaffold.insert({curr[C[i]], C[i]});

            // cerr << "remove\n";

        }
        prv[C[i]] = K+i;
    }

    // cerr << "advice = ";
    // for(int v = 0; v < N+K; v++) cerr << removed[v] << ' ';
    // cerr << '\n';

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

#include "assistant.h"
#include <set>
#include <iostream>
using namespace std;

void Assist(unsigned char *A, int N, int K, int R)
{
    set<int> good, bad;
    for(int i = 0; i < K; i++)
    {
        if(A[i]) bad.insert(i);
        else good.insert(i);
    }

    for(int i = 0; i < N; i++)
    {
        int c = GetRequest();

        if(good.find(c) == good.end() && bad.find(c) == bad.end())
        {
            int r = *bad.begin();
            bad.erase(r);
            PutBack(r);
        }

        good.erase(c);
        bad.erase(c);
        if(A[i+K])
            bad.insert(c);
        else
            good.insert(c);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 0 ms 580 KB Output is correct
3 Correct 3 ms 684 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 4 ms 696 KB Output is correct
6 Correct 5 ms 704 KB Output is correct
7 Correct 5 ms 932 KB Output is correct
8 Correct 5 ms 960 KB Output is correct
9 Correct 5 ms 900 KB Output is correct
10 Correct 9 ms 1004 KB Output is correct
11 Correct 6 ms 868 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1192 KB Output is correct
2 Correct 62 ms 3316 KB Output is correct
3 Correct 139 ms 8680 KB Output is correct
4 Correct 77 ms 5132 KB Output is correct
5 Correct 94 ms 5216 KB Output is correct
6 Correct 108 ms 5640 KB Output is correct
7 Correct 146 ms 7040 KB Output is correct
8 Correct 100 ms 6980 KB Output is correct
9 Correct 78 ms 4968 KB Output is correct
10 Correct 156 ms 8232 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 6144 KB Output is correct
2 Correct 137 ms 7464 KB Output is correct
3 Correct 164 ms 7684 KB Output is correct
4 Correct 145 ms 7588 KB Output is correct
5 Correct 163 ms 7056 KB Output is correct
6 Correct 148 ms 7676 KB Output is correct
7 Correct 152 ms 7620 KB Output is correct
8 Correct 135 ms 7608 KB Output is correct
9 Correct 146 ms 7552 KB Output is correct
10 Correct 140 ms 7580 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 7 ms 936 KB Output is correct
3 Correct 4 ms 664 KB Output is correct
4 Correct 5 ms 672 KB Output is correct
5 Correct 5 ms 672 KB Output is correct
6 Correct 4 ms 912 KB Output is correct
7 Correct 6 ms 1064 KB Output is correct
8 Correct 7 ms 912 KB Output is correct
9 Correct 7 ms 960 KB Output is correct
10 Correct 8 ms 1172 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 7100 KB Output is correct - 120000 bits used
2 Correct 141 ms 7304 KB Output is correct - 122000 bits used
3 Correct 162 ms 7688 KB Output is correct - 125000 bits used
4 Correct 139 ms 7624 KB Output is correct - 125000 bits used
5 Correct 143 ms 7640 KB Output is correct - 125000 bits used
6 Correct 154 ms 7648 KB Output is correct - 125000 bits used
7 Correct 143 ms 7552 KB Output is correct - 124828 bits used
8 Correct 165 ms 7524 KB Output is correct - 124910 bits used
9 Correct 141 ms 7568 KB Output is correct - 125000 bits used
10 Correct 172 ms 7596 KB Output is correct - 125000 bits used