#include<bits/stdc++.h>
#include "advisor.h"
using namespace std;
int andamio[100001];
queue<int> rep[100001];
pair<int,int> st[400010];
void st_i(int j,int i=0,int pos=1){
if(i==j){
int aux=andamio[i];
if(rep[aux].size()>0) aux=rep[aux].front();
else aux=100000;
st[pos]={aux,aux};
return;
}
st_i((i+j)/2,i,pos*2);
st_i(j,(i+j)/2+1,pos*2+1);
st[pos].first=max(st[pos*2].first,st[pos*2+1].second);
st[pos].second=min(st[pos*2].second,st[pos*2+1].second);
}
void st_ap(int j,int act,int i=0,int pos=1){
if(i==j){
int aux=andamio[i];
if(rep[aux].size()>0) aux=rep[aux].front();
else aux=100000;
st[pos]={aux,aux};
return;
}
if(st[pos*2].second==act) st_ap((i+j)/2,act,i,pos*2);
else st_ap(j,act,(i+j)/2+1,pos*2+1);
st[pos].first=max(st[pos*2].first,st[pos*2+1].second);
st[pos].second=min(st[pos*2].second,st[pos*2+1].second);
}
void st_ag(int j,int act,int i=0,int pos=1){
if(i==j){
int aux=andamio[i];
if(rep[aux].size()>0) aux=rep[aux].front();
else aux=100000;
st[pos]={aux,aux};
return;
}
if(st[pos*2].first==act) st_ag((i+j)/2,act,i,pos*2);
else st_ag(j,act,(i+j)/2+1,pos*2+1);
st[pos].first=max(st[pos*2].first,st[pos*2+1].second);
st[pos].second=min(st[pos*2].second,st[pos*2+1].second);
}
int return_min(int j,int i=0,int pos=1){
if(i==j) return i;
else if(st[pos].second==st[pos*2].second) return return_min((i+j)/2,i,pos*2);
else return return_min(j,(i+j)/2+1,pos*2+1);
}
int return_max(int j,int i=0,int pos=1){
if(i==j) return i;
else if(st[pos].first==st[pos*2].first) return return_max((i+j)/2,i,pos*2);
else return return_max(j,(i+j)/2+1,pos*2+1);
}
void ComputeAdvice(int *C, int N, int K, int M) {
int lim=log2(K-1);
int expo[lim+2];
expo[0]=1;
for(int i=1;i<=lim;i++){
expo[i]=expo[i-1]*2;
}
if(expo[lim]*2-1<K-1) {
lim++;
expo[lim]=expo[lim-1]*2;
}
for(int i=0;i<N;i++){
if(i<K) andamio[i]=i;
rep[C[i]].push(i);
}
st_i(K-1);
for(int i=0;i<N;i++){
//cout<<st[1].second<<endl;
if(st[1].second==i){
rep[andamio[return_min(K-1)]].pop();
st_ap(K-1,i);
}
else{
int pos=return_max(K-1);
int val=pos;
for(int j=lim;j>=0;j--){
if(expo[j]<=val){
WriteAdvice(1);
val-=expo[j];
}
else WriteAdvice(0);
}
rep[C[i]].pop();
//cout<<andamio[pos]<<endl;
andamio[pos]=C[i];
st_ag(K-1,st[i].first);
}
}
}
#include<bits/stdc++.h>
#include "assistant.h"
using namespace std;
bool cont[100001];
int an[100001];
void Assist(unsigned char *A, int N, int K, int R) {
int lim=log2(K-1);
int expo[lim+2];
expo[0]=1;
for(int i=1;i<=lim;i++){
expo[i]=expo[i-1]*2;
}
if(expo[lim]*2-1<K-1) {
lim++;
expo[lim]=expo[lim-1]*2;
}
for(int i=0;i<K;i++){
cont[i]=1;
an[i]=i;
}
int pos=0;
for(int i=0;i<N;i++){
int req=GetRequest();
if(cont[req]==false){
int val=0;
for(int j=lim;j>=0;j--){
if(A[pos]==1) val+=expo[j];
pos++;
}
cont[val]=false;
//cout<<an[val]<<endl;
PutBack(an[val]);
an[val]=req;
cont[req]=true;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
68020 KB |
Output is correct |
2 |
Incorrect |
39 ms |
68024 KB |
Error - Not putting back color when it is not on the scaffold |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
62 ms |
68664 KB |
Error - Not putting back color when it is not on the scaffold |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
295 ms |
77476 KB |
Error - Not putting back color when it is not on the scaffold |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
42 ms |
67940 KB |
Error - advice is too long |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
330 ms |
78528 KB |
Error - Not putting back color when it is not on the scaffold |
2 |
Incorrect |
315 ms |
79512 KB |
Error - Not putting back color when it is not on the scaffold |
3 |
Incorrect |
366 ms |
78288 KB |
Error - Not putting back color when it is not on the scaffold |
4 |
Incorrect |
276 ms |
78076 KB |
Error - Not putting back color when it is not on the scaffold |
5 |
Incorrect |
336 ms |
78512 KB |
Error - Not putting back color when it is not on the scaffold |
6 |
Incorrect |
283 ms |
77960 KB |
Error - Not putting back color when it is not on the scaffold |
7 |
Incorrect |
323 ms |
78060 KB |
Error - Not putting back color when it is not on the scaffold |
8 |
Incorrect |
311 ms |
78732 KB |
Error - Not putting back color when it is not on the scaffold |
9 |
Incorrect |
306 ms |
78132 KB |
Error - Not putting back color when it is not on the scaffold |
10 |
Incorrect |
276 ms |
78016 KB |
Error - Not putting back color when it is not on the scaffold |