oj.uz

Submission #517228

# Submission time Handle Problem Language Result Execution time Memory
517228 2022-01-22T18:53:40 Z Vladth11 Last supper (IOI12_supper) C++14
0 / 100
 118 ms 8512 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#include "advisor.h"
//#include "assistant.h"

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 21;
const ll INF = 2e9;
const ll MOD = 1000000007;
const ll BLOCK = 2154;
const ll base = 31;
const ll nr_of_bits = 17;

int utill[NMAX * 2];
int f[NMAX];
int nou[NMAX * 2];
int last[NMAX * 2];
int ap[NMAX];

void ComputeAdvice(int *C, int N, int K, int M) {
    priority_queue <pii> pq;

    set <pii> st;
    int cnt = 0;
    for(int i = 0; i < K; i++) {
        pq.push({last[i], i});
        f[i] = 1;
        st.insert({i, i});
    }
    for(int i = 0; i < K; i++)
        nou[i] = i;
    for(int i = K; i < K + N; i++) {
        nou[i] = C[i - K];
    }
    for(int i = 0; i < NMAX; i++) {
        ap[i] = 2e9;
    }
    for(int i = N + K - 1; i >= 0; i--) {
        last[i] = ap[nou[i]];
        ap[nou[i]] = i;
    }
    for(int i = 0; i < N; i++) {
        int request = C[i];
        auto it = st.lower_bound({request, 0});
        if(it != st.end() && (*it).first == request) {
            utill[(*it).second] = 1;
            st.erase(it);
            pq.push({last[i + K], request});
            /// nu dam f[el] = 0, fiindca inca e in coada si are o nxt aparitie mai mare
            st.insert({request, i + K});
        } else {
            while(pq.size() && f[pq.top().second] == 0)
                pq.pop();
            pii x = pq.top(); /// nici nu dam pop ca totul e safe
            st.erase(*st.lower_bound({x.second, 0}));
            f[x.second] = 0;
        }
    }
    for(int i = 0; i < N + K; i++) {
        WriteAdvice(utill[i]);
    }
}


#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
//#include "advisor.h"
#include "assistant.h"

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 21;
const ll INF = 2e9;
const ll MOD = 1000000007;
const ll BLOCK = 2154;
const ll base = 31;
const ll nr_of_bits = 17;

int utill[NMAX * 2];
int f[NMAX];
int nou[NMAX * 2];
int last[NMAX * 2];
int ap[NMAX];

void Assist(unsigned char *A, int N, int K, int R) {
    set <int> util, inutil;
    for(int i = 0; i < K; i++) {
        int utility = A[i];
        if(utility) {
            util.insert(i);
        } else {
            inutil.insert(i);
        }
    }
    for(int i = 0; i < N; i++) {
        int utility = A[i + K];
        int request = GetRequest();
        if(util.find(request) != util.end() || inutil.find(request) != inutil.end()) {
            util.erase(request);
            inutil.erase(request); /// vrem sa inlocuim cu noua chestie
        } else {
            auto it = inutil.rbegin();
            PutBack((int)*it);
            inutil.erase(*it);
        }
        if(utility) {
            util.insert(request);
        } else {
            inutil.insert(request);
        }
    }
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:30:9: warning: unused variable 'cnt' [-Wunused-variable]
   30 |     int cnt = 0;
      |         ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 988 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1632 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 Incorrect 78 ms 6728 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 7900 KB Output isn't correct - not an optimal way
2 Incorrect 97 ms 8048 KB Output isn't correct - not an optimal way
3 Incorrect 91 ms 8320 KB Output isn't correct - not an optimal way
4 Incorrect 99 ms 8408 KB Output isn't correct - not an optimal way
5 Incorrect 94 ms 8512 KB Output isn't correct - not an optimal way
6 Incorrect 91 ms 8288 KB Output isn't correct - not an optimal way
7 Incorrect 118 ms 8428 KB Output isn't correct - not an optimal way
8 Incorrect 113 ms 8276 KB Output isn't correct - not an optimal way
9 Incorrect 103 ms 8332 KB Output isn't correct - not an optimal way
10 Incorrect 88 ms 8352 KB Output isn't correct - not an optimal way