oj.uz

Submission #271532

# Submission time Handle Problem Language Result Execution time Memory
271532 2020-08-18T06:35:21 Z 최은수(#5096) Last supper (IOI12_supper) C++14
34 / 100
 545 ms 18544 KB 
#include"advisor.h"
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct seg
{
    int t[400010];
    void init(int n,int s,int e)
    {
        t[n]=0;
        if(s==e)
            return;
        int m=s+(e-s)/2;
        init(n*2,s,m);
        init(n*2+1,m+1,e);
        return;
    }
    void upd(int n,int s,int e,int x,int p)
    {
        t[n]+=p;
        if(s==e)
            return;
        int m=s+(e-s)/2;
        if(x>m)
            upd(n*2+1,m+1,e,x,p);
        else
            upd(n*2,s,m,x,p);
        return;
    }
    int query(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return 0;
        if(S<=s&&e<=E)
            return t[n];
        int m=s+(e-s)/2;
        return query(n*2,s,m,S,E)+query(n*2+1,m+1,e,S,E);
    }
    int kth(int n,int s,int e,int k)
    {
        if(s==e)
            return s;
        int m=s+(e-s)/2;
        if(k<t[n*2])
            return kth(n*2,s,m,k);
        return kth(n*2+1,m+1,e,k-t[n*2]);
    }
};
void ComputeAdvice(int*C,int N,int K,int M)
{
    set<pi,greater<pi> >st;
    vector<int>v(N,N);
    vector<int>nx=v;
    for(int i=N;i-->0;)
        nx[i]=v[C[i]],v[C[i]]=i;
    seg segt;
    segt.init(1,0,N-1);
    for(int i=0;i<K;i++)
        st.ep(v[i],i),segt.upd(1,0,N-1,i,1);
    int bpq=K==1?0:32-__builtin_clz(K-1);
    for(int i=0;i<N;i++)
    {
        auto it=st.find(pi(i,C[i]));
        if(it==st.end())
            it=st.begin();
        st.erase(it);
        int pop=it->se;
        segt.upd(1,0,N-1,pop,-1);
        int kth=segt.query(1,0,N-1,0,pop);
        for(int j=0;j<bpq;j++)
            WriteAdvice(kth>>j&1);
        st.ep(nx[i],C[i]);
        segt.upd(1,0,N-1,C[i],1);
    }
    return;
}
#include"assistant.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct seg
{
    int t[400010];
    void init(int n,int s,int e)
    {
        t[n]=0;
        if(s==e)
            return;
        int m=s+(e-s)/2;
        init(n*2,s,m);
        init(n*2+1,m+1,e);
        return;
    }
    void upd(int n,int s,int e,int x,int p)
    {
        t[n]+=p;
        if(s==e)
            return;
        int m=s+(e-s)/2;
        if(x>m)
            upd(n*2+1,m+1,e,x,p);
        else
            upd(n*2,s,m,x,p);
        return;
    }
    int query(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return 0;
        if(S<=s&&e<=E)
            return t[n];
        int m=s+(e-s)/2;
        return query(n*2,s,m,S,E)+query(n*2+1,m+1,e,S,E);
    }
    int kth(int n,int s,int e,int k)
    {
        if(s==e)
            return s;
        int m=s+(e-s)/2;
        if(k<t[n*2])
            return kth(n*2,s,m,k);
        return kth(n*2+1,m+1,e,k-t[n*2]);
    }
};
void Assist(unsigned char*A,int N,int K,int R)
{
    seg st;
    st.init(1,0,N-1);
    for(int i=0;i<K;i++)
        st.upd(1,0,N-1,i,1);
    int bpq=K==1?0:32-__builtin_clz(K-1);
    for(int i=0;i<N;i++)
    {
        int c=GetRequest();
        int kth=0;
        for(int j=0;j<bpq;j++)
            kth|=(int)A[i*bpq+j]<<j;
        int pop=st.kth(1,0,N-1,kth);
        st.upd(1,0,N-1,pop,-1);
        st.upd(1,0,N-1,c,1);
        if(pop!=c)
            PutBack(pop);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 904 KB Output is correct
2 Correct 1 ms 904 KB Output is correct
3 Correct 5 ms 948 KB Output is correct
4 Correct 5 ms 820 KB Output is correct
5 Correct 7 ms 1172 KB Output is correct
6 Correct 15 ms 1280 KB Output is correct
7 Correct 18 ms 1420 KB Output is correct
8 Correct 20 ms 1432 KB Output is correct
9 Correct 20 ms 1464 KB Output is correct
10 Correct 20 ms 1568 KB Output is correct
11 Correct 25 ms 1568 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2368 KB Output is correct
2 Correct 214 ms 7144 KB Output is correct
3 Correct 545 ms 18544 KB Output is correct
4 Correct 311 ms 9648 KB Output is correct
5 Correct 425 ms 12140 KB Output is correct
6 Correct 446 ms 14136 KB Output is correct
7 Correct 532 ms 16584 KB Output is correct
8 Correct 477 ms 15248 KB Output is correct
9 Correct 218 ms 8312 KB Output is correct
10 Correct 545 ms 17544 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 14336 KB Output is correct
2 Correct 502 ms 17360 KB Output is correct
3 Correct 498 ms 17352 KB Output is correct
4 Correct 508 ms 17096 KB Output is correct
5 Correct 485 ms 16608 KB Output is correct
6 Correct 484 ms 17608 KB Output is correct
7 Correct 487 ms 17072 KB Output is correct
8 Correct 477 ms 17152 KB Output is correct
9 Correct 504 ms 17096 KB Output is correct
10 Correct 525 ms 17096 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
8.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 16592 KB Output is partially correct - 1500000 bits used
2 Correct 521 ms 17104 KB Output is partially correct - 1500000 bits used
3 Correct 487 ms 17360 KB Output is partially correct - 1500000 bits used
4 Correct 507 ms 17168 KB Output is partially correct - 1500000 bits used
5 Correct 495 ms 17360 KB Output is partially correct - 1500000 bits used
6 Correct 513 ms 17592 KB Output is partially correct - 1500000 bits used
7 Correct 488 ms 17488 KB Output is partially correct - 1497585 bits used
8 Correct 489 ms 17104 KB Output is partially correct - 1500000 bits used
9 Correct 489 ms 17096 KB Output is partially correct - 1500000 bits used
10 Correct 486 ms 17352 KB Output is partially correct - 1500000 bits used