oj.uz

Submission #547174

# Submission time Handle Problem Language Result Execution time Memory
547174 2022-04-09T18:33:58 Z Jesus Last supper (IOI12_supper) C++14
43 / 100
 280 ms 78496 KB 
#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=100001;
        st[pos]={aux,aux};
        return;
    }
    st[pos*2]={-1,1000000};
    st[pos*2+1]=st[pos*2];
    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].first);
    st[pos].second=min(st[pos*2].second,st[pos*2+1].second);
}

int act;
void st_ap(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=100001;
        st[pos]={aux,aux};
        return;
    }
    if(st[pos*2].second==act) st_ap((i+j)/2,i,pos*2);
    else st_ap(j,(i+j)/2+1,pos*2+1);
    st[pos].first=max(st[pos*2].first,st[pos*2+1].first);
    st[pos].second=min(st[pos*2].second,st[pos*2+1].second);
}

void st_ag(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=100001;
        st[pos]={aux,aux};
        return;
    }
    if(st[pos*2].first==act) st_ag((i+j)/2,i,pos*2);
    else st_ag(j,(i+j)/2+1,pos*2+1);
    st[pos].first=max(st[pos*2].first,st[pos*2+1].first);
    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;
    if(K==1) lim=0;
    else 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++){
        if(st[1].second==i){
            rep[andamio[return_min(K-1)]].pop();
            act=i;
            st_ap(K-1);
        }
        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];
            act=st[1].first;
            st_ag(K-1);

        }
    }
}

#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;
    if(K==1) lim=0;
    else 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){
                cont[i]=true;
                an[i]=i;
        }
        else cont[i]=false;
    }

    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((int)A[pos]==1) val+=expo[j];
                pos++;
            }
            cont[an[val]]=false;
            //cout<<an[val]<<endl;
            PutBack(an[val]);
            an[val]=req;
            cont[req]=true;


        }
    }

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 67796 KB Output is correct
2 Correct 41 ms 67736 KB Output is correct
3 Correct 41 ms 67812 KB Output is correct
4 Correct 41 ms 68104 KB Output is correct
5 Correct 43 ms 68248 KB Output is correct
6 Correct 51 ms 68212 KB Output is correct
7 Correct 46 ms 68236 KB Output is correct
8 Correct 51 ms 68280 KB Output is correct
9 Correct 50 ms 68260 KB Output is correct
10 Correct 44 ms 68336 KB Output is correct
11 Correct 48 ms 68272 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 68616 KB Output is correct
2 Correct 114 ms 71352 KB Output is correct
3 Correct 257 ms 78216 KB Output is correct
4 Correct 189 ms 74612 KB Output is correct
5 Correct 244 ms 76580 KB Output is correct
6 Correct 266 ms 76860 KB Output is correct
7 Correct 239 ms 76564 KB Output is correct
8 Correct 232 ms 76824 KB Output is correct
9 Correct 151 ms 73360 KB Output is correct
10 Correct 226 ms 75848 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 73712 KB Output is correct
2 Correct 237 ms 74992 KB Output is correct
3 Correct 229 ms 74984 KB Output is correct
4 Correct 224 ms 74628 KB Output is correct
5 Correct 196 ms 73416 KB Output is correct
6 Correct 236 ms 76160 KB Output is correct
7 Correct 233 ms 75916 KB Output is correct
8 Correct 278 ms 78496 KB Output is correct
9 Correct 184 ms 74184 KB Output is correct
10 Correct 234 ms 76280 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 68080 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 75272 KB Output is partially correct - 772365 bits used
2 Correct 230 ms 75124 KB Output is partially correct - 742095 bits used
3 Correct 235 ms 74908 KB Output is partially correct - 712470 bits used
4 Correct 233 ms 74900 KB Output is partially correct - 712005 bits used
5 Correct 232 ms 74996 KB Output is partially correct - 710610 bits used
6 Correct 231 ms 74896 KB Output is partially correct - 712155 bits used
7 Correct 227 ms 74944 KB Output is partially correct - 711090 bits used
8 Correct 231 ms 74948 KB Output is partially correct - 713340 bits used
9 Correct 227 ms 75000 KB Output is partially correct - 712830 bits used
10 Correct 280 ms 77352 KB Output is partially correct - 1117620 bits used