Submission #373497

#	Time	Username	Problem	Language	Result	Execution time	Memory
373497		WLZ	Last supper (IOI12_supper)	C++14	100 / 100	157 ms	9240 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

void ComputeAdvice(int *C, int N, int K, int M) {
  vector<int> last(N, INF), next(N, INF), in(N, -1), ans(N + K, 0);
  for (int i = N - 1; i >= 0; i--) {
    next[i] = last[C[i]];
    last[C[i]] = i;
  }
  set< pair<int, int> > st;
  for (int i = 0; i < K; i++) {
    st.insert({last[i], i});
    in[i] = i;
  }
  for (int i = 0; i < N; i++) {
    if (in[C[i]] == -1) {
      auto p = *st.rbegin();
      in[p.second] = -1;
      st.erase(p);
      st.insert({next[i], C[i]});
      in[C[i]] = K + i;
    } else {
      ans[in[C[i]]] = 1;
      st.erase({i, C[i]});
      st.insert({next[i], C[i]});
      in[C[i]] = K + i;
    }
  }
  for (int i = 0; i < N + K; i++) WriteAdvice(ans[i]);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
  vector< set<int> > v(2);
  vector<int> in(N, -1);
  for (int i = 0; i < K; i++) {
    v[A[i]].insert(i);
    in[i] = A[i];
  }
  for (int i = 0; i < N; i++) {
    int x = GetRequest();
    if (in[x] == -1) {
      auto y = *v[0].begin();
      PutBack(y);
      v[in[y]].erase(y);
      in[y] = -1;
      in[x] = A[K + i];
      v[in[x]].insert(x);
    } else {
      v[in[x]].erase(x);
      in[x] = A[K + i];
      v[in[x]].insert(x);
    }
  }
}

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