Submission #1229526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229526		chaeryeong	Last supper (IOI12_supper)	C++20	43 / 100	186 ms	7260 KiB

advisor

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

void ComputeAdvice (int *c, int n, int k, int m) {
  vector <int> nxt(n, n), first(n, n);
  for (int i = n - 1; i >= 0; i--) {
    nxt[i] = first[c[i]];
    first[c[i]] = i;
  }
  set <pair <int, int>> ii;
  set <int> jj;
  vector <int> pp(n, -1);
  for (int i = 0; i < k; i++) {
    pp[i] = i;
    ii.insert({first[i], i});
    jj.insert(i);
  }
  vector <int> e(n, 0);
  for (int i = 0; i < n; i++) {
    if (jj.count(c[i])) {
      e[i] = -1; continue;
    }
    while ((*(ii.begin())).first <= i) {
      auto x = *(ii.begin());
      ii.erase(x);
      ii.insert({nxt[x.first], x.second});
    }
    auto x = *(--ii.end());
    ii.erase(x); jj.erase(x.second);

    e[i] = pp[x.second];
    assert(e[i] != -1);
    pp[c[i]] = pp[x.second];
    pp[x.second] = -1;

    ii.insert({nxt[i], c[i]});
    jj.insert(c[i]);
  }
  int f = __lg(k) + 1;
  for (int i = 0; i < n; i++) {
    if (e[i] == -1) {
      continue;
    }
    for (int b = 0; b < f; b++) {
      WriteAdvice((e[i] >> b) & 1);
    }
  }
}

assistant

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

void Assist (unsigned char *a, int n, int k, int r) {
  int bit = 0;
  int f = __lg(k) + 1;
  vector <int> cur(k, 0);
  iota(cur.begin(), cur.end(), 0);
  vector <int> vis(n, 0);
  for (int i = 0; i < k; i++) {
    vis[i] = 1;
  }
  for (int i = 0; i < n; i++) {
    int x = GetRequest();
    if (!vis[x]) {
      int idx = 0;
      for (int j = 0; j < f; j++) {
        if (a[bit++] == 1) {
          idx |= 1 << j;
        }
      }
      PutBack(cur[idx]);
      vis[cur[idx]] = 0;
      vis[x] = 1;
      cur[idx] = x;
    }
  }
}

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