Submission #49102

#	Time	Username	Problem	Language	Result	Execution time	Memory
49102		hamzqq9	Last supper (IOI12_supper)	C++14	100 / 100	299 ms	28880 KiB

advisor

#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define pll pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1050000000
#define MAXN 200005
#define LOG 20
#define magic 100
#define KOK 700
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
//#include "grader.h"
using namespace std;
#include "advisor.h"

static int act[MAXN];

void ComputeAdvice(int *C, int N, int K, int M) {

  memset(act,0,sizeof(act));

  vector<int> v;

  int last[MAXN],nxt[MAXN],prv[MAXN];

  for(int i=0;i<K;i++) v.pb(i);

  for(int i=0;i<N;i++) v.pb(C[i]);

  int sz=N+K;

  memset(last,-1,sizeof(last));

  for(int i=sz-1;i>=0;i--) {

    if(~last[v[i]]) {

      nxt[i]=last[v[i]];

    }
    else {

      nxt[i]=sz;

    }

    last[v[i]]=i;

  }

  memset(last,-1,sizeof(last));

  for(int i=0;i<sz;i++) {

    if(~last[v[i]]) {

      prv[i]=last[v[i]];

    }
    else {

      prv[i]=-1;

    }

    last[v[i]]=i;

  }

  set<ii> s;

  for(int i=0;i<sz;i++) {

    if(sz(s)<K) {

      s.insert({nxt[i],v[i]});

    }
    else {

      auto plc=s.find({i,v[i]});

      if(plc!=s.end()) {

        if(prv[i]!=-1) act[prv[i]]=1;

        s.erase(plc);

      }
      else {

        auto it=prev(s.end());

        s.erase(it);

      }

      s.insert({nxt[i],v[i]});

    }

  } 

  for(int i=0;i<sz;i++) {

    WriteAdvice(act[i]);

  }

}

assistant

#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define pll pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1050000000
#define MAXN 200005
#define LOG 20
#define magic 100
#define KOK 700
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
//#include "grader.h"
using namespace std;
#include "assistant.h"

void Assist(unsigned char *A, int N, int K, int R) {

  set<int> del,alle;

  for(int i=0;i<K;i++) {

    if(!A[i]) {

      del.insert(i);

    }

    alle.insert(i);

  }

  for(int i=0;i<N;i++) {

    int want=GetRequest();
    unsigned char now=A[i+K];

    if(now) {

      if(alle.find(want)==alle.end()) {
      
        alle.insert(want); 

        int val=*del.begin();

        del.erase(del.begin());

        alle.erase(alle.find(val));

        PutBack(val);

      }

    } 
    else {

      if(alle.find(want)==alle.end()) {

        alle.insert(want); 

        int val=*del.begin();

        del.erase(del.begin());

        alle.erase(alle.find(val));

        PutBack(val);

      }

      del.insert(want);

    }

  }

}

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