oj.uz

Submission #914435

# Submission time Handle Problem Language Result Execution time Memory
914435 2024-01-22T05:58:53 Z Ghulam_Junaid Last supper (IOI12_supper) C++17
0 / 100
 262 ms 19500 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

void ComputeAdvice(int *C, int N, int K, int M){
    int lg = 0;
    for (int i=0; i<20; i++){
        if ((1 << i) > N){
            lg = i;
            break;
        }
    }


    vector<int> g[N];
    int use[N] = {0};
    for (int i=0; i<N; i++)
        g[i].push_back(N + 1);
    for (int i=N-1; i>=0; i--)
        g[C[i]].push_back(i);

    for (int i=0; i<N; i++)
        use[i] = g[i].back();

    set<pair<int, int>> st;
    for (int i=0; i<K; i++)
        st.insert({use[i], i});

    for (int i=0; i<N; i++){
        if (st.find({use[C[i]], C[i]}) != st.end()){
            st.erase({use[C[i]], C[i]});
            g[C[i]].pop_back();
            use[C[i]] = g[C[i]].back();
            st.insert({use[C[i]], C[i]});
            continue;
        }

        auto p = *st.rbegin();
        
        int c = p.second;
        g[c].pop_back();

        if (g[c].size())
            use[c] = g[c].back();

        for (int j=0; j<lg; j++){
            if ((1 << j) & c){
                WriteAdvice(1);
            }
            else{
                WriteAdvice(0);
            }
        }

        // cout << "erasing " << c << " and getting " << C[i] << endl;

        st.erase(p);

        g[C[i]].pop_back();
        use[C[i]] = g[C[i]].back();

        st.insert({use[C[i]], C[i]});
    }
}

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

using namespace std;

void Assist(unsigned char *A, int N, int K, int R){
    int lg = 0;
    for (int i=0; i<20; i++){
        if ((1 << i) > N){
            lg = i;
            break;
        }
    }

    set<int> st;
    for (int i=0; i<K; i++)
        st.insert(i);

    // cout << endl;

    int ind = 0;
    for (int i=0; i<N; i++){
        int x = GetRequest();
        if (st.find(x) != st.end())
            continue;

        int c = 0;
        for (int j=0; j<lg; j++)
            if ((int)A[ind + j])
                c += (1 << j);

        PutBack(c);
        st.erase(c);
        st.insert(x);

        // cout << "putting back " << c << endl;

        ind += lg;
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 784 KB Output is correct
2 Correct 0 ms 784 KB Output is correct
3 Correct 1 ms 936 KB Output is correct
4 Incorrect 7 ms 1132 KB Output isn't correct - not an optimal way
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2572 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 13748 KB Output is correct
2 Correct 212 ms 16984 KB Output is correct
3 Correct 220 ms 16980 KB Output is correct
4 Correct 204 ms 16760 KB Output is correct
5 Incorrect 166 ms 15296 KB Output isn't correct - not an optimal way
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1056 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 17120 KB Output isn't correct - not an optimal way
2 Correct 209 ms 16708 KB Output is partially correct - 841041 bits used
3 Correct 223 ms 16756 KB Output is partially correct - 807466 bits used
4 Correct 209 ms 16808 KB Output is partially correct - 806939 bits used
5 Correct 202 ms 16776 KB Output is partially correct - 805358 bits used
6 Correct 210 ms 17024 KB Output is partially correct - 807109 bits used
7 Correct 206 ms 16948 KB Output is partially correct - 805902 bits used
8 Correct 222 ms 16916 KB Output is partially correct - 808452 bits used
9 Correct 212 ms 16788 KB Output is partially correct - 807874 bits used
10 Correct 262 ms 19500 KB Output is partially correct - 1266636 bits used