oj.uz

Submission #986914

# Submission time Handle Problem Language Result Execution time Memory
986914 2024-05-21T14:42:05 Z Sharky Last supper (IOI12_supper) C++17
0 / 100
 108 ms 150096 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

void ComputeAdvice(int *C, int N, int K, int M) {
    vector<int> req(N + K, 0);
    for (int i = 0; i < K; i++) req[i] = i;
    for (int i = K; i < N + K; i++) req[i] = C[i - K];
    vector<int> s(N + K, 0);
    vector<vector<int>> add(N), del(N);
    vector<queue<int>> pos(N);
    vector<bool> scaff(N, 0);
    for (int i = 0; i < N + K; i++) {
        pos[req[i]].push(i);
        scaff[i] = true;
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (int i = 0; i < N + K; i++) {
        if (!scaff[req[i]]) {
            auto [dist, col] = pq.top();
            pq.pop();
            del[col].push_back(i);
            scaff[col] = false;
            scaff[req[i]] = true;
        }
        pos[req[i]].pop();
        int tp = inf;
        if (!pos[req[i]].empty()) tp = pos[req[i]].front();
        pq.push({tp, req[i]});
        add[req[i]].push_back(i);
    }
    for (int i = 0; i < N; i++) del[i].push_back(N + K);
    for (int i = 0; i < N + K; i++) {
        auto it = upper_bound(add[req[i]].begin(), add[req[i]].end(), i);
        int k = *lower_bound(del[req[i]].begin(), del[req[i]].end(), i);
        if (it == add[req[i]].end() || (*it) > k) s[i] = 1;
        WriteAdvice(s[i]);
    }
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
    assert(R == N + K);
    vector<set<int>> st(2);
    vector<bool> scaff(N, 0);
    for (int i = 0; i < K; i++) {
        st[A[i]].insert(i);
        scaff[i] = true;
    }
    for (int i = K; i < N + K; i++) {
        int req = GetRequest();
        if (!st[1].empty() && !scaff[req]) {
            int f = *st[1].begin();
            st[1].erase(f);
            PutBack(f);
            scaff[f] = false;
            scaff[req] = true;
        }
        st[0].erase(req);
        st[A[i]].insert(req);
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 792 KB Output is correct
2 Correct 1 ms 780 KB Output is correct
3 Runtime error 3 ms 1884 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 15452 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 120660 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 6492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 149704 KB Execution killed with signal 6
2 Runtime error 95 ms 149904 KB Execution killed with signal 6
3 Runtime error 93 ms 149832 KB Execution killed with signal 6
4 Runtime error 95 ms 149844 KB Execution killed with signal 6
5 Runtime error 102 ms 150096 KB Execution killed with signal 6
6 Runtime error 95 ms 149876 KB Execution killed with signal 6
7 Runtime error 93 ms 149672 KB Execution killed with signal 6
8 Runtime error 96 ms 149888 KB Execution killed with signal 6
9 Runtime error 108 ms 149836 KB Execution killed with signal 6
10 Runtime error 94 ms 149988 KB Execution killed with signal 6