oj.uz

Submission #993206

# Submission time Handle Problem Language Result Execution time Memory
993206 2024-06-05T12:40:27 Z 12345678 Last supper (IOI12_supper) C++17
100 / 100
 118 ms 21200 KB 
#include "advisor.h"
#include <bits/stdc++.h>

using namespace std;

const int nxx=1e5+5;

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

void ComputeAdvice(int *C, int N, int K, int M) {
    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;
            rem[col].push_back(i);
            mx.erase(prev(mx.end()));
            d[C[i]].pop_back();
        }
        if (d[C[i]].empty()) mx.insert({1e9, C[i]});
        else mx.insert({d[C[i]].back(), C[i]});
    }
    for (int i=0; i<N; i++) d[i].clear(), rem[i].push_back(1e8), reverse(rem[i].begin(), rem[i].end());
    for (int i=N-1; i>=0; i--) d[C[i]].push_back(i);
    for (int i=0; i<K; i++)
    {
        if (d[i].empty()||d[i].back()>rem[i].back()) WriteAdvice(1);
        else WriteAdvice(0);
    }
    for (int i=0; i<N; i++)
    {
        d[C[i]].pop_back();
        while (rem[C[i]].back()<i) rem[C[i]].pop_back();
        if (d[C[i]].empty()||d[C[i]].back()>rem[C[i]].back()) WriteAdvice(1);
        else WriteAdvice(0);
    }
}
#include "assistant.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

set<int> s;
queue<int> q;

void Assist(unsigned char *A, int N, int K, int R) {
    for (int i=0; i<K; i++) if (A[i]) q.push(i);
    for (int i=0; i<K; i++) s.insert(i);
    for (int i=0; i<N; i++)
    {
        int t=GetRequest();
        if (s.find(t)==s.end())
        {
            s.erase(q.front());
            PutBack(q.front());
            q.pop();
            s.insert(t);
        }
        if (A[i+K]) q.push(t);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8224 KB Output is correct
2 Correct 3 ms 8236 KB Output is correct
3 Correct 5 ms 8236 KB Output is correct
4 Correct 4 ms 8520 KB Output is correct
5 Correct 8 ms 8544 KB Output is correct
6 Correct 6 ms 8536 KB Output is correct
7 Correct 6 ms 8536 KB Output is correct
8 Correct 7 ms 8808 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 7 ms 8668 KB Output is correct
11 Correct 6 ms 8852 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8996 KB Output is correct
2 Correct 49 ms 12572 KB Output is correct
3 Correct 118 ms 21200 KB Output is correct
4 Correct 91 ms 17040 KB Output is correct
5 Correct 109 ms 17096 KB Output is correct
6 Correct 91 ms 17632 KB Output is correct
7 Correct 97 ms 19120 KB Output is correct
8 Correct 93 ms 19044 KB Output is correct
9 Correct 83 ms 16124 KB Output is correct
10 Correct 107 ms 20048 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 17408 KB Output is correct
2 Correct 105 ms 19524 KB Output is correct
3 Correct 106 ms 19520 KB Output is correct
4 Correct 98 ms 19356 KB Output is correct
5 Correct 91 ms 18504 KB Output is correct
6 Correct 100 ms 19632 KB Output is correct
7 Correct 99 ms 19632 KB Output is correct
8 Correct 98 ms 20552 KB Output is correct
9 Correct 79 ms 18276 KB Output is correct
10 Correct 102 ms 19432 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 5 ms 8536 KB Output is correct
4 Correct 4 ms 8544 KB Output is correct
5 Correct 5 ms 8536 KB Output is correct
6 Correct 5 ms 8544 KB Output is correct
7 Correct 5 ms 8540 KB Output is correct
8 Correct 8 ms 8544 KB Output is correct
9 Correct 6 ms 8536 KB Output is correct
10 Correct 6 ms 9064 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 18992 KB Output is correct - 120000 bits used
2 Correct 100 ms 19256 KB Output is correct - 122000 bits used
3 Correct 105 ms 19636 KB Output is correct - 125000 bits used
4 Correct 100 ms 19568 KB Output is correct - 125000 bits used
5 Correct 102 ms 19472 KB Output is correct - 125000 bits used
6 Correct 101 ms 19516 KB Output is correct - 125000 bits used
7 Correct 102 ms 19520 KB Output is correct - 124828 bits used
8 Correct 102 ms 19724 KB Output is correct - 124910 bits used
9 Correct 105 ms 19660 KB Output is correct - 125000 bits used
10 Correct 95 ms 20608 KB Output is correct - 125000 bits used