oj.uz

Submission #154022

# Submission time Handle Problem Language Result Execution time Memory
154022 2019-09-17T17:53:04 Z stefdasca Last supper (IOI12_supper) C++14
100 / 100
 457 ms 148360 KB 
#include<bits/stdc++.h>
#include "advisor.h"
using namespace std;


deque<int>v[100002];
void ComputeAdvice(int *C, int N, int K, int M)
{
    for(int i = 0; i < N; ++i)
        v[C[i]].push_back(i);
    for(int i = 0; i < N; ++i)
        v[i].push_back((1<<20));
    set<pair<int, int> >cb;
    set<int>nr;
    for(int i = 0; i < K; ++i)
        cb.insert({v[i][0], i}), nr.insert(i);
    int act[100002];
    memset(act, 0, sizeof(act));
    int st[100002];
    for(int i = 0; i < K; ++i)
        st[i] = 1;
    int saved[100002];
    memset(saved, 0, sizeof(saved));
    int prv[100002];
    memset(prv, -1, sizeof(prv));
    for(int i = 0; i < N; ++i)
    {
        if(nr.find(C[i]) != nr.end())
        {
            if(C[i] < K && !saved[C[i]])
                saved[C[i]] = 1;
            cb.erase({v[C[i]][0], C[i]});
            v[C[i]].pop_front();
            cb.insert({v[C[i]][0], C[i]});
            if(prv[C[i]] != -1)
                act[prv[C[i]]] = 1;
            prv[C[i]] = i;
        }
        else
        {
            if((*cb.rbegin()).second < K)
            {
                int val = (*cb.rbegin()).second;
                if(val < K && !saved[val])
                    st[val] = 0, saved[val] = 1;
            }
            nr.erase((*cb.rbegin()).second);
            cb.erase(*cb.rbegin());
            nr.insert(C[i]);
            v[C[i]].pop_front();
            cb.insert({v[C[i]][0], C[i]});
            prv[C[i]] = i;
        }
    }
    for(int i = 0; i < K; ++i)
        WriteAdvice(st[i]);
    for(int i = 0; i < N; ++i)
        WriteAdvice(act[i]);
}

#include<bits/stdc++.h>
#include "assistant.h"
using namespace std;

void Assist(unsigned char *A, int N, int K, int R)
{
    int frq[100002];
    memset(frq, 0, sizeof(frq));
    int poz = 0;
    for(int i = 0; i < R; ++i)
    {
        if(A[i] == 1)
            ++poz;
        else
            ++frq[poz];
    }
    set<int>good;
    set<int>bad;
    for(int i = 0; i < K; ++i)
        if(A[i] == 1)
            good.insert(i);
        else
            bad.insert(i);
    for(int i = 0; i < N; ++i)
    {
        int req = GetRequest();
        if(bad.find(req) == bad.end() && good.find(req) == good.end())
        {
            PutBack(*bad.begin());
            bad.erase(bad.begin());
            if(A[i + K] == 1)
                good.insert(req);
            else
                bad.insert(req);
        }
        else
            if(bad.find(req) == bad.end())
            {
                good.erase(req);
                if(A[i + K] == 1)
                    good.insert(req);
                else
                    bad.insert(req);
            }
            else
            {
                bad.erase(req);
                if(A[i + K] == 1)
                    good.insert(req);
                else
                    bad.insert(req);
            }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 137968 KB Output is correct
2 Correct 74 ms 137712 KB Output is correct
3 Correct 77 ms 138232 KB Output is correct
4 Correct 77 ms 137712 KB Output is correct
5 Correct 79 ms 137712 KB Output is correct
6 Correct 80 ms 137912 KB Output is correct
7 Correct 81 ms 137968 KB Output is correct
8 Correct 81 ms 137968 KB Output is correct
9 Correct 100 ms 137944 KB Output is correct
10 Correct 88 ms 138224 KB Output is correct
11 Correct 84 ms 138080 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 138488 KB Output is correct
2 Correct 179 ms 140296 KB Output is correct
3 Correct 411 ms 148360 KB Output is correct
4 Correct 218 ms 141296 KB Output is correct
5 Correct 259 ms 141552 KB Output is correct
6 Correct 289 ms 142584 KB Output is correct
7 Correct 359 ms 145392 KB Output is correct
8 Correct 288 ms 145648 KB Output is correct
9 Correct 217 ms 141296 KB Output is correct
10 Correct 425 ms 147440 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 144432 KB Output is correct
2 Correct 381 ms 146344 KB Output is correct
3 Correct 377 ms 146200 KB Output is correct
4 Correct 417 ms 146416 KB Output is correct
5 Correct 397 ms 145392 KB Output is correct
6 Correct 448 ms 146328 KB Output is correct
7 Correct 457 ms 146344 KB Output is correct
8 Correct 329 ms 146288 KB Output is correct
9 Correct 395 ms 146416 KB Output is correct
10 Correct 388 ms 146360 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 137848 KB Output is correct
2 Correct 82 ms 137968 KB Output is correct
3 Correct 82 ms 137968 KB Output is correct
4 Correct 80 ms 137920 KB Output is correct
5 Correct 87 ms 137888 KB Output is correct
6 Correct 90 ms 138136 KB Output is correct
7 Correct 101 ms 137968 KB Output is correct
8 Correct 87 ms 138080 KB Output is correct
9 Correct 101 ms 137912 KB Output is correct
10 Correct 91 ms 138768 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 145408 KB Output is correct - 120000 bits used
2 Correct 366 ms 146104 KB Output is correct - 122000 bits used
3 Correct 378 ms 145392 KB Output is correct - 125000 bits used
4 Correct 383 ms 145392 KB Output is correct - 125000 bits used
5 Correct 380 ms 145136 KB Output is correct - 125000 bits used
6 Correct 375 ms 145536 KB Output is correct - 125000 bits used
7 Correct 385 ms 145392 KB Output is correct - 124828 bits used
8 Correct 373 ms 145392 KB Output is correct - 124910 bits used
9 Correct 383 ms 145392 KB Output is correct - 125000 bits used
10 Correct 376 ms 145392 KB Output is correct - 125000 bits used