oj.uz

Submission #1083134

# Submission time Handle Problem Language Result Execution time Memory
1083134 2024-09-02T16:12:14 Z codefox Last supper (IOI12_supper) C++14
100 / 100
 74 ms 8616 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;
#define pii pair<int, int>

void ComputeAdvice(int *C, int N, int K, int M)
{
    int H = K+N;
    vector<int> next(H, 0);
    vector<int> last(N, 1e9);
    for (int i = N-1; i >= 0; i--)
    {
        next[i+K] = last[C[i]];
        last[C[i]]=i+K;
    }
    for (int i = 0; i < K; i++)
    {
        next[i] = last[i];
    }
    set<pii> follow;
    vector<int> first(N, -1);
    vector<int> ins(N, 0);
    vector<int> del(N+K, 0);

    vector<int> CC(H);
    for (int i = 0; i < K; i++) CC[i] = i;
    for (int i = 0; i < N; i++) CC[i+K] = C[i];

    for (int i = 0; i < K; i++)
    {
        first[i] = i;
        follow.insert({next[i], i});
        ins[i] = 1;
    }
    for (int i = K; i < H; i++)
    {
        if (ins[CC[i]])
        {
            follow.erase({i, first[CC[i]]});
            follow.insert({next[i], i});
        }
        else
        {
            pii ab = *(--follow.end());
            follow.erase(ab);
            ins[CC[ab.second]] = 0;
            del[ab.second] = 1;
            ins[CC[i]] = 1;
            follow.insert({next[i], i});
        }
        first[CC[i]] = i;
    }
    for (int i = 0; i < H; i++)
    {
        WriteAdvice(del[i]);
    }
}

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

using namespace std;

void Assist(unsigned char *A, int N, int K, int R)
{
    queue<int> del;
    vector<int> ins(N, 0);
    for (int i = 0; i < K; i++)
    {
        ins[i] = 1;
        if (A[i]) del.push(i);
    }
    for (int i = K; i < N+K; i++)
    {
        int g = GetRequest();
        if (!ins[g])
        {
            ins[del.front()]=0;
            ins[g] = 1;
            PutBack(del.front());
            del.pop();
        }
        if (A[i]) del.push(g);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 784 KB Output is correct
2 Correct 0 ms 784 KB Output is correct
3 Correct 1 ms 800 KB Output is correct
4 Correct 1 ms 824 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 3 ms 1096 KB Output is correct
7 Correct 4 ms 1096 KB Output is correct
8 Correct 3 ms 1104 KB Output is correct
9 Correct 3 ms 1096 KB Output is correct
10 Correct 3 ms 1204 KB Output is correct
11 Correct 3 ms 1092 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1424 KB Output is correct
2 Correct 26 ms 4004 KB Output is correct
3 Correct 60 ms 8616 KB Output is correct
4 Correct 36 ms 6536 KB Output is correct
5 Correct 43 ms 6420 KB Output is correct
6 Correct 45 ms 7028 KB Output is correct
7 Correct 61 ms 7732 KB Output is correct
8 Correct 45 ms 7020 KB Output is correct
9 Correct 45 ms 6500 KB Output is correct
10 Correct 61 ms 8280 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6536 KB Output is correct
2 Correct 57 ms 8036 KB Output is correct
3 Correct 66 ms 8032 KB Output is correct
4 Correct 65 ms 8084 KB Output is correct
5 Correct 62 ms 7836 KB Output is correct
6 Correct 60 ms 8044 KB Output is correct
7 Correct 63 ms 8008 KB Output is correct
8 Correct 52 ms 8008 KB Output is correct
9 Correct 48 ms 8040 KB Output is correct
10 Correct 57 ms 8092 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1096 KB Output is correct
2 Correct 4 ms 1096 KB Output is correct
3 Correct 3 ms 1096 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 4 ms 1104 KB Output is correct
6 Correct 3 ms 1188 KB Output is correct
7 Correct 3 ms 1092 KB Output is correct
8 Correct 3 ms 1092 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 4 ms 1356 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 7816 KB Output is correct - 120000 bits used
2 Correct 57 ms 7744 KB Output is correct - 122000 bits used
3 Correct 74 ms 8004 KB Output is correct - 125000 bits used
4 Correct 59 ms 8000 KB Output is correct - 125000 bits used
5 Correct 59 ms 8008 KB Output is correct - 125000 bits used
6 Correct 56 ms 8004 KB Output is correct - 125000 bits used
7 Correct 59 ms 8008 KB Output is correct - 124828 bits used
8 Correct 59 ms 8020 KB Output is correct - 124910 bits used
9 Correct 60 ms 7852 KB Output is correct - 125000 bits used
10 Correct 56 ms 8008 KB Output is correct - 125000 bits used