oj.uz

Submission #561957

# Submission time Handle Problem Language Result Execution time Memory
561957 2022-05-13T23:44:39 Z Jesus Last supper (IOI12_supper) C++14
100 / 100
 158 ms 74216 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);
}

char valor[200002];

int ult[100001];

void ComputeAdvice(int *C, int N, int K, int M) {
    for(int i=0;i<N;i++){
        if(i<K) {
                andamio[i]=i;
                valor[i]=1;
                ult[i]=i;
        }
        rep[C[i]].push(i);
    }
    st_i(K-1);


    for(int i=0;i<N;i++){
        valor[i+K]=1;
        if(st[1].second==i){
            int pos=andamio[return_min(K-1)];
            rep[pos].pop();
            act=i;
            st_ap(K-1);
            ult[pos]=i+K;
        }
        else{
            int pos=return_max(K-1);
            valor[ult[andamio[pos]]]=0;
            rep[C[i]].pop();
            andamio[pos]=C[i];
            act=st[1].first;
            st_ag(K-1);
            ult[C[i]]=i+K;
        }
    }
    for(int i=0;i<N+K;i++){
        WriteAdvice(valor[i]);
    }
}

/*10 3 200
6 2 2 1 3 6 9 8 6 2*/

#include<bits/stdc++.h>
#include "assistant.h"

using namespace std;

queue<int> lib;

int an[100001];

int col[100001];

void Assist(unsigned char *A, int N, int K, int R){
    for(int i=0;i<N;i++){
        if(i<K){
            an[i]=i;
            col[i]=i;
            if(A[i]==0) lib.push(i);
        }
        else col[i]=-1;
    }

    for(int i=0;i<N;i++){
        int c=GetRequest();
        if(col[c]==-1){
            int pos=0;
            if(lib.size()>0){
                pos=lib.front();
                lib.pop();
            }
            PutBack(an[pos]);
            col[an[pos]]=-1;
            col[c]=pos;
            an[pos]=c;
        }
        if(A[i+K]==0) lib.push(col[c]);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 67756 KB Output is correct
2 Correct 41 ms 67764 KB Output is correct
3 Correct 44 ms 68124 KB Output is correct
4 Correct 44 ms 68020 KB Output is correct
5 Correct 44 ms 68344 KB Output is correct
6 Correct 42 ms 68088 KB Output is correct
7 Correct 45 ms 68212 KB Output is correct
8 Correct 47 ms 68084 KB Output is correct
9 Correct 44 ms 68104 KB Output is correct
10 Correct 42 ms 68112 KB Output is correct
11 Correct 46 ms 68112 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 68256 KB Output is correct
2 Correct 94 ms 70632 KB Output is correct
3 Correct 142 ms 74216 KB Output is correct
4 Correct 105 ms 72524 KB Output is correct
5 Correct 110 ms 72648 KB Output is correct
6 Correct 144 ms 72880 KB Output is correct
7 Correct 130 ms 73328 KB Output is correct
8 Correct 107 ms 72688 KB Output is correct
9 Correct 103 ms 72544 KB Output is correct
10 Correct 133 ms 73432 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 72440 KB Output is correct
2 Correct 138 ms 73424 KB Output is correct
3 Correct 140 ms 73496 KB Output is correct
4 Correct 133 ms 73552 KB Output is correct
5 Correct 143 ms 73368 KB Output is correct
6 Correct 139 ms 73592 KB Output is correct
7 Correct 146 ms 73468 KB Output is correct
8 Correct 124 ms 73440 KB Output is correct
9 Correct 152 ms 73388 KB Output is correct
10 Correct 143 ms 73472 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 68152 KB Output is correct
2 Correct 44 ms 68356 KB Output is correct
3 Correct 43 ms 68172 KB Output is correct
4 Correct 43 ms 68272 KB Output is correct
5 Correct 45 ms 68432 KB Output is correct
6 Correct 43 ms 68100 KB Output is correct
7 Correct 42 ms 68372 KB Output is correct
8 Correct 51 ms 68332 KB Output is correct
9 Correct 46 ms 68064 KB Output is correct
10 Correct 42 ms 68408 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 73372 KB Output is correct - 120000 bits used
2 Correct 158 ms 73416 KB Output is correct - 122000 bits used
3 Correct 136 ms 73488 KB Output is correct - 125000 bits used
4 Correct 138 ms 73424 KB Output is correct - 125000 bits used
5 Correct 137 ms 73372 KB Output is correct - 125000 bits used
6 Correct 129 ms 73480 KB Output is correct - 125000 bits used
7 Correct 138 ms 73388 KB Output is correct - 124828 bits used
8 Correct 130 ms 73424 KB Output is correct - 124910 bits used
9 Correct 137 ms 73396 KB Output is correct - 125000 bits used
10 Correct 126 ms 73492 KB Output is correct - 125000 bits used