Submission #987526

#	Time	Username	Problem	Language	Result	Execution time	Memory
987526		huutuan	Last supper (IOI12_supper)	C++14	100 / 100	211 ms	146064 KiB

advisor

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

using namespace std;

static const int N=2e5+10;

static queue<int> v[N];
static bool on[N];
static int del[N], nxt[N];
static int add[N];

void ComputeAdvice(int *c, int n, int k, int m){
   int lg=32-__builtin_clz(k);
   for (int i=0; i<n; ++i) v[c[i]].push(i+1);
   for (int i=0; i<n; ++i) v[i].push(n+1);
   set<pair<int, int>, greater<pair<int, int>>> pq;
   for (int i=0; i<=n+k; ++i) nxt[i]=del[i]=n+1;
   for (int i=0; i<k; ++i) pq.emplace(v[i].front(), i), on[i]=1, add[i]=0, nxt[i]=v[i].front();
   for (int t=1; t<=n; ++t){
      int x=c[t-1];
      pq.erase({v[x].front(), x});
      v[x].pop();
      add[x]=t;
      nxt[t+k]=v[x].front();
      if (!on[x]){
         int y=pq.begin()->second; pq.erase(pq.begin());
         if (!add[y]){
            del[y]=t;
         }else{
            del[add[y]+k]=t;
         }
         on[y]=0;
         on[x]=1;
      }
      pq.emplace(v[x].front(), x);
   }
   for (int i=0; i<k; ++i) WriteAdvice(nxt[i]<del[i]);
   for (int i=k+1; i<=n+k; ++i) WriteAdvice(nxt[i]<del[i]);
}

assistant

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

using namespace std;

void Assist(unsigned char *a, int n, int k, int r){
   int lg=32-__builtin_clz(k);
   vector<int> v(k);
   iota(v.begin(), v.end(), 0);
   int cur=0;
   set<int> st(v.begin(), v.end());
   vector<int> q;
   for (int i=0; i<k; ++i){
      int y=a[cur++];
      if (!y) q.push_back(i);
   }
   for (int i=0; i<n; ++i){
      int x=GetRequest();
      int y=a[cur++];
      if (!st.count(x)){
         PutBack(q.back()); st.erase(q.back());
         st.insert(x);
         q.pop_back();
      }
      if (!y) q.push_back(x);
   }
}

Compilation message (stderr)

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:14:8: warning: unused variable 'lg' [-Wunused-variable]
   14 |    int lg=32-__builtin_clz(k);
      |        ^~

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:7:8: warning: unused variable 'lg' [-Wunused-variable]
    7 |    int lg=32-__builtin_clz(k);
      |        ^~

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