oj.uz

Submission #990485

# Submission time Handle Problem Language Result Execution time Memory
990485 2024-05-30T14:15:54 Z 12345678 Last supper (IOI12_supper) C++17
43 / 100
 197 ms 18928 KB 
#include "advisor.h"
#include <bits/stdc++.h>

using namespace std;

const int nxx=1e5+5;

int bits;
vector<int> d[nxx], idx(nxx);
set<pair<int, int>> mx;

void ComputeAdvice(int *C, int N, int K, int M) {
    bits=ceil(log2(K));
    for (int i=N-1; i>=0; i--) d[C[i]].push_back(i);
    for (int i=0; i<K; i++)
    {
        idx[i]=i;
        if (d[i].empty()) mx.insert({1e9, i});
        else mx.insert({d[i].back(), i});
    }
    for (int i=0; i<N; i++)
    {
        if (mx.find({i, C[i]})!=mx.end())
        {
            d[C[i]].pop_back();
            mx.erase({i, C[i]});
        }
        else
        {
            auto col=prev(mx.end())->second;
            mx.erase(prev(mx.end()));
            d[C[i]].pop_back();
            idx[C[i]]=idx[col];
            for (int j=0; j<bits; j++) WriteAdvice((idx[C[i]]&(1<<j))!=0); 
            //cout<<"remove "<<C[i]<<' '<<idx[C[i]]<<'\n';
        }
        if (d[C[i]].empty()) mx.insert({1e9, C[i]});
        else mx.insert({d[C[i]].back(), C[i]});
    }
}
#include "assistant.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int c[nx], bit, t;
set<int> s;

void Assist(unsigned char *A, int N, int K, int R) {
    bit=ceil(log2(K));
    for (int i=0; i<K; i++) c[i]=i, s.insert(i);
    for (int i=0; i<N; i++)
    {
        auto cur=GetRequest();
        if (s.find(cur)!=s.end()) continue;
        int tmp=0;
        for (int j=0; j<bit; j++) if (A[t++]==1) tmp+=(1<<j);
        s.erase(c[tmp]);
        PutBack(c[tmp]);
        s.insert(cur);
        c[tmp]=cur;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3616 KB Output is correct
2 Correct 1 ms 3624 KB Output is correct
3 Correct 1 ms 3628 KB Output is correct
4 Correct 3 ms 3664 KB Output is correct
5 Correct 3 ms 3664 KB Output is correct
6 Correct 7 ms 3980 KB Output is correct
7 Correct 4 ms 3920 KB Output is correct
8 Correct 7 ms 4008 KB Output is correct
9 Correct 8 ms 3988 KB Output is correct
10 Correct 6 ms 4088 KB Output is correct
11 Correct 7 ms 3984 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4556 KB Output is correct
2 Correct 59 ms 7772 KB Output is correct
3 Correct 182 ms 18092 KB Output is correct
4 Correct 106 ms 12108 KB Output is correct
5 Correct 161 ms 13996 KB Output is correct
6 Correct 163 ms 14728 KB Output is correct
7 Correct 162 ms 15180 KB Output is correct
8 Correct 153 ms 16728 KB Output is correct
9 Correct 125 ms 9632 KB Output is correct
10 Correct 159 ms 15676 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 11956 KB Output is correct
2 Correct 157 ms 15136 KB Output is correct
3 Correct 159 ms 15224 KB Output is correct
4 Correct 150 ms 14660 KB Output is correct
5 Correct 126 ms 12772 KB Output is correct
6 Correct 162 ms 15256 KB Output is correct
7 Correct 152 ms 14992 KB Output is correct
8 Correct 197 ms 18928 KB Output is correct
9 Correct 103 ms 12196 KB Output is correct
10 Correct 157 ms 15064 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 14120 KB Output is partially correct - 772365 bits used
2 Correct 158 ms 14104 KB Output is partially correct - 742095 bits used
3 Correct 159 ms 14196 KB Output is partially correct - 712470 bits used
4 Correct 157 ms 14352 KB Output is partially correct - 712005 bits used
5 Correct 155 ms 14132 KB Output is partially correct - 710610 bits used
6 Correct 157 ms 13972 KB Output is partially correct - 712155 bits used
7 Correct 163 ms 13964 KB Output is partially correct - 711090 bits used
8 Correct 157 ms 14200 KB Output is partially correct - 713340 bits used
9 Correct 157 ms 13980 KB Output is partially correct - 712830 bits used
10 Correct 185 ms 17604 KB Output is partially correct - 1117620 bits used