Submission #1270275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270275		StefanSebez	Last supper (IOI12_supper)	C++20	0 / 100	200 ms	14580 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=1e5+50,lg=13,inf=1e9;
struct Node{int maks,i;};
Node Merge(Node a,Node b){if(a.maks>=b.maks) return a;return b;}
struct SegTree{
    int root,nc,lc[2*N],rc[2*N];Node node[2*N];
    SegTree(){node[0]={-inf,0};}
    void Update(int &c,int ss,int se,int qind,int qval){
        if(!c) c=++nc,node[c]={-inf,ss};
        if(ss==se){node[c]={qval,ss};return;}
        int mid=ss+se>>1;
        if(qind<=mid)Update(lc[c],ss,mid,qind,qval);
        else Update(rc[c],mid+1,se,qind,qval);
        node[c]=Merge(node[lc[c]],node[rc[c]]);
    }
    Node Get(int c,int ss,int se,int qs,int qe){
        if(qs>qe||qe<ss||se<qs)return {-inf,0};
        if(qs<=ss&&se<=qe)return node[c];
        int mid=ss+se>>1;
        return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
    }
}ST;
vector<int>ind[N];
void ComputeAdvice(int *C, int n, int K, int m1) {
    vector<int>ids;
    for(int i=0;i<n;i++) ind[C[i]].pb(i);
    for(int i=0;i<=n;i++) ind[i].pb(inf);
    map<int,int>mapa;
    int niz[K+10];
    for(int i=0;i<K;i++){
        mapa[i]++;niz[i]=i;
        int lb=lower_bound(ind[i].begin(),ind[i].end(),0)-ind[i].begin();
        int x=ind[i][lb];
        //printf("%i: %i\n",i,x);
        ST.Update(ST.root,0,K-1,i,x);
    }
    //for(int j=0;j<K;j++) printf("%i ",ST.Get(ST.root,0,K-1,j,j).maks);printf("\n");
    for(int i=0;i<n;i++){
        if(mapa[C[i]]>0){ids.pb(K);continue;}
        Node x=ST.node[ST.root];
        ids.pb(x.i);
        int lb=lower_bound(ind[C[i]].begin(),ind[C[i]].end(),i+1)-ind[C[i]].begin();
        int y=ind[C[i]][lb];
        ST.Update(ST.root,0,K-1,x.i,y);
        mapa[niz[x.i]]--;
        mapa[C[i]]++;
        niz[x.i]=C[i];
        //for(int j=0;j<K;j++) printf("%i ",ST.Get(ST.root,0,K-1,j,j).maks);printf("\n");
    }
    //for(auto i:ids) printf("%i ",i);printf("\n");
    for(auto i:ids){
        for(int j=0;j<lg;j++){
            WriteAdvice(i>>j&1);
        }
    }
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=1e5+50,lg=13;
int ids[N];
void Assist(unsigned char *A, int n, int K, int m){
    for(int i=0;i<m;i++){
        if(A[i]==1) ids[i/lg]^=1<<(i%lg);
    }
    /*for(int i=0;i*lg+lg<=m;i++){
        for(int j=i*lg,k=0;j<i*lg+lg;j++,k++){
            if(A[j]==1) ids[i]^=1<<k;
        }
    }*/
    int niz[K+10];
    for(int i=0;i<K;i++) niz[i]=i;
    for(int i=0;i<n;i++){
        int x=GetRequest();
        if(ids[i]>=K) continue;
        PutBack(niz[ids[i]]);
        niz[ids[i]]=x;
    }
    /*for (int i = 0; i < N; i++) {
    int req = GetRequest();
    if (req >= K)
      PutBack(req % K);
    }*/
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 35
• Subtask 5: 0 / 39