This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
typedef pair<int,int> pii;
vector<int> nxt[100001],rem[100001];
bool have[100001],init[100001],ad[100001];
int n;
int go(int color,int cur){
vector<int>::iterator it = upper_bound(nxt[color].begin(),nxt[color].end(),cur);
if(it == nxt[color].end())
return n;
return *it;
}
bool active(int color , int idx){
int nxt = go(color,idx);
vector<int>::iterator it = upper_bound(rem[color].begin(),rem[color].end(),idx);
int nxR = 0;
if(it == rem[color].end())
nxR = n;
else
nxR = *it;
if(nxt < nxR)
return 1;
return 0;
}
void ComputeAdvice(int *C, int N, int K, int M) {
n = N;
for (int i = 0; i < N; ++i) {
nxt[C[i]].push_back(i);
}
set< pii > q;
for (int i = 0; i < K; ++i) {
have[i] = 1;
q.insert(make_pair(go(i, -1), i));
}
for (int i = 0; i < N; i++) {
int req = C[i];
if (have[req]) {
q.erase(make_pair(go(req, i - 1), req));
q.insert(make_pair(go(req, i), req));
continue;
}
pii src = (*(--q.end()));
q.erase(src);
rem[src.second].push_back(i);
have[src.second] = 0;
have[req] = 1;
q.insert(make_pair(go(req, i), req));
}
//cout << "INITIAL " << endl;
for (int i = 0; i < K; ++i){
WriteAdvice(active(i,-1));
// cout << "THERE " << active(i,-1) << endl;
}
//cout << "REQUESTS" << endl;
for (int i = 0; i < N; ++i){
WriteAdvice(active(C[i],i));
//cout << C[i] << " -> " << active(C[i],i) << endl;
}
}
#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
typedef pair<int,int> pii;
bool hold[100001],state[100001];
set<int> passive;
void Assist(unsigned char *A, int N, int K, int R) {
for (int i = 0; i < R; ++i){
if(i >= K){
state[i-K] = A[i];
}else{
hold[i] = 1;
if(A[i] == 0){
passive.insert(i);
}
}
}
for (int i = 0; i < N; ++i){
int req = GetRequest();
if(!hold[req]){
PutBack(*passive.begin());
hold[*passive.begin()] = 0;
hold[req] = 1;
passive.erase(passive.begin());
}
if(state[i] == 1){
passive.erase(req);
}else{
passive.insert(req);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |