oj.uz

Submission #256262

# Submission time Handle Problem Language Result Execution time Memory
256262 2020-08-02T12:43:16 Z Akashi Last supper (IOI12_supper) C++14
100 / 100
 106 ms 7152 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

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

    vector <int> ap(N, N);
    vector <int> Next(N, N);
    for (int i = N - 1; i >= 0 ; --i) {
        Next[i] = ap[C[i]];
        ap[C[i]] = i;
    }

    vector <bool> adv(M, 1);

    set <pair <int, int> > s;
    vector <bool> f(N, 0);

    for (int i = 0; i < K ; ++i) {
        s.insert({ap[i], i});
        f[i] = 1;
    }

    for (int i = 0; i < N ; ++i) {
        if (f[C[i]] == 1) {
            set <pair <int, int> > :: iterator it = s.lower_bound({i, 0});
            s.erase(it);
        } else {
            ///trebuie sa scot o culoare de pe paleta
            set <pair <int, int> > :: reverse_iterator it = s.rbegin();
            adv[it->second] = 0;
            if (it->second < K) f[it->second] = 0;
            else f[C[it->second - K]] = 0;
            s.erase(*it);
        }

        f[C[i]] = 1;
        s.insert({Next[i], i + K});
    }

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

    return ;
}


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

void Assist(unsigned char *A, int N, int K, int R) {
    vector <bool> f(N, 0);
    vector <int> rec;

    int ind = 0;
    for (int i = 0; i < K ; ++i, ++ind) {
        if (A[ind] == 0) rec.push_back(i);
        f[i] = 1;
    }

    for (int i = 0; i < N ; ++i, ++ind) {
        int req = GetRequest();
        if (!f[req]) {
            f[req] = 1;
            f[rec.back()] = 0;
            PutBack(rec.back());
            rec.pop_back();
        }

        if (A[ind] == 0) rec.push_back(req);
    }

    return ;
}
/**
4 2 65000
2 0 3 0
**/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 772 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 2 ms 968 KB Output is correct
4 Correct 3 ms 792 KB Output is correct
5 Correct 4 ms 968 KB Output is correct
6 Correct 6 ms 960 KB Output is correct
7 Correct 8 ms 952 KB Output is correct
8 Correct 8 ms 1184 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 7 ms 1128 KB Output is correct
11 Correct 5 ms 1024 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1536 KB Output is correct
2 Correct 46 ms 2816 KB Output is correct
3 Correct 103 ms 7152 KB Output is correct
4 Correct 71 ms 3824 KB Output is correct
5 Correct 77 ms 3824 KB Output is correct
6 Correct 83 ms 4336 KB Output is correct
7 Correct 96 ms 5616 KB Output is correct
8 Correct 80 ms 5616 KB Output is correct
9 Correct 70 ms 3736 KB Output is correct
10 Correct 103 ms 6448 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 4848 KB Output is correct
2 Correct 98 ms 5872 KB Output is correct
3 Correct 98 ms 5872 KB Output is correct
4 Correct 100 ms 5872 KB Output is correct
5 Correct 99 ms 5360 KB Output is correct
6 Correct 100 ms 6128 KB Output is correct
7 Correct 100 ms 5872 KB Output is correct
8 Correct 94 ms 5872 KB Output is correct
9 Correct 96 ms 5872 KB Output is correct
10 Correct 99 ms 5872 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1192 KB Output is correct
2 Correct 6 ms 1136 KB Output is correct
3 Correct 4 ms 808 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 7 ms 808 KB Output is correct
6 Correct 5 ms 808 KB Output is correct
7 Correct 5 ms 940 KB Output is correct
8 Correct 7 ms 1192 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 6 ms 1312 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5488 KB Output is correct - 120000 bits used
2 Correct 96 ms 5872 KB Output is correct - 122000 bits used
3 Correct 98 ms 6136 KB Output is correct - 125000 bits used
4 Correct 98 ms 6128 KB Output is correct - 125000 bits used
5 Correct 100 ms 6128 KB Output is correct - 125000 bits used
6 Correct 99 ms 6128 KB Output is correct - 125000 bits used
7 Correct 104 ms 6128 KB Output is correct - 124828 bits used
8 Correct 106 ms 6128 KB Output is correct - 124910 bits used
9 Correct 104 ms 6128 KB Output is correct - 125000 bits used
10 Correct 92 ms 6128 KB Output is correct - 125000 bits used