Submission #517232

#	Time	Username	Problem	Language	Result	Execution time	Memory
517232		Vladth11	Last supper (IOI12_supper)	C++14	100 / 100	206 ms	9948 KiB

advisor

#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]);
    }
}

assistant

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39