oj.uz

Submission #362875

# Submission time Handle Problem Language Result Execution time Memory
362875 2021-02-04T14:32:00 Z 79brue Last supper (IOI12_supper) C++14
100 / 100
 261 ms 17880 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

typedef long long ll;

struct dat{
    int l, r, x;
    dat(){}
    dat(int l, int r, int x): l(l), r(r), x(x){}

    bool operator<(const dat &nxt)const{
        if(r != nxt.r) return r<nxt.r;
        return x < nxt.x;
    }
};

int n, k, m;
int arr[100002];
vector<int> occurence[100002];
set<dat> st;
set<int> now;
vector<bool> bits;
int loc[100002];

void ComputeAdvice(int *C, int N, int K, int M){
    n = N, k = K, m = M;
    bits.resize(n+k);
    for(int i=0; i<n; i++){
        arr[i] = C[i];
        occurence[arr[i]].push_back(i);
    }
    for(int i=0; i<n; i++){
        occurence[i].push_back(1e9);
        reverse(occurence[i].begin(), occurence[i].end());
    }

    for(int i=0; i<k; i++){
        now.insert(i);
        st.insert(dat(i, occurence[i].back(), i));
        loc[i] = i;
    }

    for(int i=0; i<n; i++){
        occurence[arr[i]].pop_back();
        if(now.find(arr[i]) != now.end()){
            auto it = st.find(dat(loc[i], i, arr[i]));
//            printf("to erase: %d %d %d\n", it->l, it->r, it->x);
            st.erase(st.find(dat(loc[i], i, arr[i])));
            st.insert(dat(k+i, occurence[arr[i]].back(), arr[i]));
            loc[arr[i]] = k+i;
            continue;
        }
//        printf("content of st: ");
//        for(auto it = st.begin(); it != st.end(); ++it) printf("(%d %d %d) ", it->l, it->r, it->x);
//        puts("");
        dat tmp = *st.rbegin();
        st.erase(prev(st.end()));
        now.erase(tmp.x);
        bits[tmp.l] = true;

        st.insert(dat(k+i, occurence[arr[i]].back(), arr[i]));
        now.insert(arr[i]);
        loc[arr[i]] = k+i;
    }

    for(int i=0; i<n+k; i++){
        WriteAdvice(bits[i]);
    }
    return;
}

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

using namespace std;

typedef long long ll;

namespace {
    int n, k, r;
    bool arr[200002];
    vector<int> order;
    set<int> st;
    stack<int> stk;
}

void Assist(unsigned char *A, int N, int K, int R){
    n = N, k = K, r = R;
    assert(r = n+k);
    for(int i=0; i<r; i++) arr[i] = A[i];
    for(int i=0; i<k; i++){
        order.push_back(i);
        st.insert(i);
        if(arr[i]) stk.push(i);
    }

    for(int i=k; i<n+k; i++){
        int tmp = GetRequest();
        order.push_back(tmp);
        if(st.find(tmp) == st.end()){
            int tmp2 = stk.top();
            PutBack(tmp2);
            stk.pop();

            st.erase(tmp2);
            st.insert(tmp);
        }
        if(arr[i]) stk.push(tmp);
    }
    return;
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:48:18: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   48 |             auto it = st.find(dat(loc[i], i, arr[i]));
      |                  ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3224 KB Output is correct
2 Correct 2 ms 3048 KB Output is correct
3 Correct 4 ms 3360 KB Output is correct
4 Correct 5 ms 3352 KB Output is correct
5 Correct 7 ms 3504 KB Output is correct
6 Correct 9 ms 3504 KB Output is correct
7 Correct 8 ms 3632 KB Output is correct
8 Correct 11 ms 3824 KB Output is correct
9 Correct 12 ms 3632 KB Output is correct
10 Correct 13 ms 3892 KB Output is correct
11 Correct 10 ms 4024 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4360 KB Output is correct
2 Correct 82 ms 8256 KB Output is correct
3 Correct 260 ms 17880 KB Output is correct
4 Correct 129 ms 11844 KB Output is correct
5 Correct 145 ms 11908 KB Output is correct
6 Correct 191 ms 12752 KB Output is correct
7 Correct 247 ms 14836 KB Output is correct
8 Correct 170 ms 14244 KB Output is correct
9 Correct 103 ms 12176 KB Output is correct
10 Correct 255 ms 16452 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 12700 KB Output is correct
2 Correct 224 ms 15480 KB Output is correct
3 Correct 225 ms 15672 KB Output is correct
4 Correct 244 ms 15776 KB Output is correct
5 Correct 210 ms 15104 KB Output is correct
6 Correct 231 ms 15752 KB Output is correct
7 Correct 245 ms 15856 KB Output is correct
8 Correct 200 ms 15584 KB Output is correct
9 Correct 193 ms 15864 KB Output is correct
10 Correct 228 ms 15608 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3868 KB Output is correct
2 Correct 8 ms 3804 KB Output is correct
3 Correct 8 ms 3632 KB Output is correct
4 Correct 8 ms 3516 KB Output is correct
5 Correct 9 ms 3632 KB Output is correct
6 Correct 9 ms 3632 KB Output is correct
7 Correct 10 ms 3844 KB Output is correct
8 Correct 10 ms 3792 KB Output is correct
9 Correct 10 ms 3764 KB Output is correct
10 Correct 12 ms 4280 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 14180 KB Output is correct - 120000 bits used
2 Correct 230 ms 14868 KB Output is correct - 122000 bits used
3 Correct 237 ms 15108 KB Output is correct - 125000 bits used
4 Correct 236 ms 15284 KB Output is correct - 125000 bits used
5 Correct 252 ms 15032 KB Output is correct - 125000 bits used
6 Correct 261 ms 14904 KB Output is correct - 125000 bits used
7 Correct 229 ms 15088 KB Output is correct - 124828 bits used
8 Correct 231 ms 14904 KB Output is correct - 124910 bits used
9 Correct 235 ms 15176 KB Output is correct - 125000 bits used
10 Correct 206 ms 15164 KB Output is correct - 125000 bits used