oj.uz

Submission #1038277

# Submission time Handle Problem Language Result Execution time Memory
1038277 2024-07-29T15:21:13 Z idas Last supper (IOI12_supper) C++11
100 / 100
 159 ms 11044 KB 
#include <bits/stdc++.h>
#include "advisor.h"

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define s second
#define f first

using namespace std;
typedef pair<int, int> pii;

namespace advisor{
    const int MxN=2e5+10, INF=1e9;
    int n, k, c[MxN], nxt[MxN], cur[MxN];
    unsigned char bits[MxN];
}

using namespace advisor;

void ComputeAdvice(int *C, int N, int K, int M) {
    n=N; k=K; FOR(i, 0, n) c[i]=C[i], cur[i]=INF;
    for(int i=n-1; i>=0; i--){
        nxt[i+k]=cur[c[i]];
        cur[c[i]]=i;
    }
    FOR(i, 0, k) nxt[i]=cur[i];
    FOR(i, 0, n+k) bits[i]=0;

    set<pii> cols;
    set<pii, greater<pii>> st;
    FOR(i, 0, k) st.insert({nxt[i],i}), cols.insert({i,i});

    FOR(i, 0, n)
    {
        auto src=cols.lower_bound({c[i],0});
        if(src!=cols.end() && (*src).f==c[i]){
            auto it=src;
            int in=(*it).s;

            st.erase({nxt[in],in});
            cols.erase(it);

            cols.insert({c[i],i+k});
            st.insert({nxt[i+k],i+k});
        }
        else{
            auto it=st.begin();
            int in=(*it).s;
            bits[in]=1;

//            cout << "rem: " << in << endl;
            st.erase(it);

            int col;
            if(in<k) col=in;
            else col=c[in-k];
            cols.erase({col,in});

            cols.insert({c[i],i+k});
            st.insert({nxt[i+k],i+k});
        }
    }

    FOR(i, 0, n+k) WriteAdvice(bits[i]);

//    FOR(i, 0, n+k) cout << int(bits[i]);
//    cout << endl;
}

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

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef vector<int> vi;

void Assist(unsigned char *bits, int n, int k, int r) {

    vi bad;
    set<int> cols;
    FOR(i, 0, k)
    {
        cols.insert(i);
        if(bits[i]==1) bad.pb(i);
    }

//    FOR(i, 0, n+k) cout << bits[i];
//    cout << endl;

//    cout << "bad: ";
//    for(auto it : bad) cout << it << " ";
//    cout << endl;

    FOR(i, k, n+k)
    {
        int next_col=GetRequest();
        if(!cols.count(next_col)){
            cols.erase(bad.back());
            PutBack(bad.back());
            bad.pop_back();
        }
        if(bits[i]==1) bad.pb(next_col);
        cols.insert(next_col);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2832 KB Output is correct
2 Correct 0 ms 2844 KB Output is correct
3 Correct 1 ms 2848 KB Output is correct
4 Correct 3 ms 2860 KB Output is correct
5 Correct 2 ms 2868 KB Output is correct
6 Correct 5 ms 2868 KB Output is correct
7 Correct 4 ms 2872 KB Output is correct
8 Correct 5 ms 2872 KB Output is correct
9 Correct 5 ms 2868 KB Output is correct
10 Correct 7 ms 3136 KB Output is correct
11 Correct 4 ms 3124 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3176 KB Output is correct
2 Correct 46 ms 4640 KB Output is correct
3 Correct 126 ms 10568 KB Output is correct
4 Correct 68 ms 6748 KB Output is correct
5 Correct 84 ms 6684 KB Output is correct
6 Correct 125 ms 7660 KB Output is correct
7 Correct 127 ms 9528 KB Output is correct
8 Correct 106 ms 9412 KB Output is correct
9 Correct 67 ms 6600 KB Output is correct
10 Correct 159 ms 11044 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 7520 KB Output is correct
2 Correct 119 ms 8956 KB Output is correct
3 Correct 130 ms 10404 KB Output is correct
4 Correct 138 ms 10404 KB Output is correct
5 Correct 134 ms 9516 KB Output is correct
6 Correct 132 ms 10400 KB Output is correct
7 Correct 135 ms 10368 KB Output is correct
8 Correct 109 ms 10376 KB Output is correct
9 Correct 117 ms 10372 KB Output is correct
10 Correct 152 ms 10304 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3124 KB Output is correct
2 Correct 6 ms 3124 KB Output is correct
3 Correct 3 ms 2876 KB Output is correct
4 Correct 2 ms 2872 KB Output is correct
5 Correct 4 ms 2876 KB Output is correct
6 Correct 6 ms 2864 KB Output is correct
7 Correct 5 ms 2868 KB Output is correct
8 Correct 6 ms 3132 KB Output is correct
9 Correct 8 ms 3124 KB Output is correct
10 Correct 6 ms 3644 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 8440 KB Output is correct - 120000 bits used
2 Correct 119 ms 8556 KB Output is correct - 122000 bits used
3 Correct 151 ms 9320 KB Output is correct - 125000 bits used
4 Correct 119 ms 9468 KB Output is correct - 125000 bits used
5 Correct 143 ms 9116 KB Output is correct - 125000 bits used
6 Correct 132 ms 9112 KB Output is correct - 125000 bits used
7 Correct 130 ms 9208 KB Output is correct - 124828 bits used
8 Correct 113 ms 9212 KB Output is correct - 124910 bits used
9 Correct 124 ms 9116 KB Output is correct - 125000 bits used
10 Correct 139 ms 9112 KB Output is correct - 125000 bits used