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"
#define pb push_back
using namespace std;
const int MM = 2e6 + 5;
bool onn[MM];
vector <int> st[MM];
void ComputeAdvice(int *C, int N, int K, int M) {
int BL = sqrt(N);
for (int i=N-1;i>=0;i--){
st[C[i]].pb(i);
}
set <pair<int,int> > stt;
for (int i=0;i<K;i++){
onn[i] = 1;
int val = 0;
if (!st[i].size()) val=1e9;
else val=st[i].back();
stt.insert({val,i});
}
int i;
vector <int> vec;
for (i = 0; i < N; i++) {
int req = C[i];
if (onn[req]) {
vec.pb(-1);
int val = 0;
if (!st[req].size()) val=1e9;
else val=st[req].back();
stt.erase(stt.find({val,req}));
while (st[req].size() && st[req].back() <= i){
st[req].pop_back();
}
val = 0;
if (!st[req].size()) val=1e9;
else val=st[req].back();
stt.insert({val,req});
continue;
}
int idx=(--stt.end())->second; stt.erase(--stt.end());
vec.pb(idx);
onn[idx] = 0;
onn[req] = 1;
while (st[req].size() && st[req].back() <= i){
st[req].pop_back();
}
int val = 0;
if (!st[req].size()) val=1e9;
else val=st[req].back();
stt.insert({val,req});
}
int bt = log2(N/BL);
for (int x: vec){
if (x==-1) continue;
int blID = x / BL;
for (int j = bt; j >= 0; j--){
if (((blID >> j) & 1)) WriteAdvice(1);
else WriteAdvice(0);
}
int iID = x - blID * BL;
for (int j = bt; j >= 0; j--){
if (((iID >> j) & 1)) WriteAdvice(1);
else WriteAdvice(0);
}
}
}
#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
int CC[2000005];
bool on[2000005];
void Assist(unsigned char *A, int N, int K, int R) {
int BL = sqrt(N);
int bt = log2(N/BL);
int id=0;
for (int i = 0; i < R; i += bt + 1){
for (int j = i; j <= i + bt; j++){
if (A[j] == 1) CC[id] |= (1<<(bt-(j-i)));
}
id+=1;
}
for (int i=0;i<K;i++) on[i] = 1;
int i;
int l = 0;
for (i = 0; i < N; i++) {
int req = GetRequest();
if (on[req]) {
continue;
}
int blID = CC[l++];
int iID = CC[l++];
int idx = blID * BL + iID;
PutBack(idx);
on[idx] = 0;
on[req] = 1;
}
}
# | 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... |