oj.uz

Submission #517232

# Submission time Handle Problem Language Result Execution time Memory
517232 2022-01-22T19:07:12 Z Vladth11 Last supper (IOI12_supper) C++14
100 / 100
 206 ms 9948 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++)
        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 < K; i++) {
        pq.push({last[i], i});
        f[i] = 1;
        st.insert({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) {
            /// A fost util si l stergem
            utill[(*it).second] = 1;
            st.erase(it);
            ///
        } else {
            /// Stergem pe cel care apare cel mai tarziu
            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;
        }
        /// Adaugam noul element
        pq.push({last[i + K], request});
        st.insert({request, i + K});
        f[request] = 1;
    }
    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:29:9: warning: unused variable 'cnt' [-Wunused-variable]
   29 |     int cnt = 0;
      |         ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 3 ms 1120 KB Output is correct
4 Correct 4 ms 1120 KB Output is correct
5 Correct 5 ms 1328 KB Output is correct
6 Correct 9 ms 1300 KB Output is correct
7 Correct 11 ms 1412 KB Output is correct
8 Correct 6 ms 1340 KB Output is correct
9 Correct 9 ms 1328 KB Output is correct
10 Correct 8 ms 1432 KB Output is correct
11 Correct 7 ms 1424 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1600 KB Output is correct
2 Correct 74 ms 4140 KB Output is correct
3 Correct 206 ms 9948 KB Output is correct
4 Correct 92 ms 6284 KB Output is correct
5 Correct 111 ms 6472 KB Output is correct
6 Correct 131 ms 6936 KB Output is correct
7 Correct 185 ms 8532 KB Output is correct
8 Correct 100 ms 7736 KB Output is correct
9 Correct 91 ms 6348 KB Output is correct
10 Correct 162 ms 9568 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 6368 KB Output is correct
2 Correct 188 ms 9028 KB Output is correct
3 Correct 160 ms 9100 KB Output is correct
4 Correct 186 ms 9068 KB Output is correct
5 Correct 163 ms 8520 KB Output is correct
6 Correct 176 ms 9124 KB Output is correct
7 Correct 164 ms 9052 KB Output is correct
8 Correct 114 ms 8780 KB Output is correct
9 Correct 154 ms 8996 KB Output is correct
10 Correct 155 ms 9112 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1288 KB Output is correct
2 Correct 9 ms 1404 KB Output is correct
3 Correct 7 ms 1432 KB Output is correct
4 Correct 5 ms 1320 KB Output is correct
5 Correct 6 ms 1320 KB Output is correct
6 Correct 6 ms 1320 KB Output is correct
7 Correct 8 ms 1328 KB Output is correct
8 Correct 7 ms 1444 KB Output is correct
9 Correct 7 ms 1448 KB Output is correct
10 Correct 11 ms 1796 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 7464 KB Output is correct - 120000 bits used
2 Correct 156 ms 7636 KB Output is correct - 122000 bits used
3 Correct 169 ms 7908 KB Output is correct - 125000 bits used
4 Correct 156 ms 7936 KB Output is correct - 125000 bits used
5 Correct 172 ms 7948 KB Output is correct - 125000 bits used
6 Correct 156 ms 7892 KB Output is correct - 125000 bits used
7 Correct 182 ms 7892 KB Output is correct - 124828 bits used
8 Correct 197 ms 7984 KB Output is correct - 124910 bits used
9 Correct 158 ms 7980 KB Output is correct - 125000 bits used
10 Correct 163 ms 7552 KB Output is correct - 125000 bits used