Submission #1211705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211705		rxlfd314	Last supper (IOI12_supper)	C++20	100 / 100	87 ms	4168 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

void ComputeAdvice(int *C, int N, int K, int M) {
  vt<int> nxt(N + K, N + K), last(N, N + K);
  ROF(i, N-1, 0) {
    nxt[i + K] = last[C[i]];
    last[C[i]] = i + K;
  }
  FOR(i, 0, K-1)
    nxt[i] = last[i];
  
  vt<int> active(N);
  fill(active.begin(), active.begin() + K, 1);
  iota(last.begin(), last.begin() + K, 0);
  
  set<ari2> take;
  FOR(i, 0, K-1)
    take.insert({nxt[i], i});
  vt<int> A(N + K);
  FOR(i, 0, N-1) {
    if (!active[C[i]]) {
      const auto [_, j] = *--take.end();
      take.erase(--take.end());
      active[j] = 0;
      A[last[j]] = 1;
      #ifdef DEBUG
      cout << "swapped: " << C[i] << ' ' << j << '\n';
      #endif
    } else {
      take.erase(take.find({i + K, C[i]}));
    }
    last[C[i]] = i + K;
    active[C[i]] = 1;
    take.insert({nxt[i + K], C[i]});
  }
  
  #ifdef DEBUG
  cout << "A:";
  for (const auto &i : A)
    cout << ' ' << i;
  cout << '\n';
  #endif
  
  for (const auto &i : A)
    WriteAdvice(i);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

void Assist(unsigned char *A, int N, int K, int R) {
  vt<int> active(N);
  set<int> take;
  FOR(i, 0, K-1) {
    if (A[i])
      take.insert(i);
    active[i] = 1;
  }
  FOR(i, K, N+K-1) {
    const int c = GetRequest();
    if (!active[c]) {
      assert(size(take));
      const int j = *take.begin();
      take.erase(take.begin());
      active[j] = 0;
      PutBack(j);
    }
    active[c] = 1;
    if (A[i])
      take.insert(c);
  }
}

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