Submission #599699

#	Time	Username	Problem	Language	Result	Execution time	Memory
599699		Soumya1	Last supper (IOI12_supper)	C++17	100 / 100	223 ms	13816 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
void ComputeAdvice(int *C, int n, int k, int M) {
  vector<int> l[n];
  for (int i = 0; i < k; i++) l[i].push_back(i);
  for (int i = 0; i < n; i++) l[C[i]].push_back(k + i);
  for (int i = 0; i < n; i++) l[i].push_back(n + k + 100);
  set<pair<int, int>> cur;
  set<int> in;
  auto to = [&](int i, int j) {
    return *upper_bound(l[i].begin(), l[i].end(), j);
  };
  auto from = [&](int i, int j) {
    auto it = lower_bound(l[i].begin(), l[i].end(), j);
    return *(--it);
  };
  for (int i = 0; i < k; i++) cur.insert({-to(i, i), i}), in.insert(i);
  vector<int> to_remove(n + k);
  for (int i = 0; i < n; i++) {
    if (in.find(C[i]) != in.end()) {
      cur.erase({-k - i, C[i]});
      cur.insert({-to(C[i], k + i), C[i]});
      continue;
    }
    auto [idx, rem] = *cur.begin();
    idx *= -1;
    to_remove[from(rem, idx)] = 1;
    cur.erase(cur.begin());
    in.erase(rem);
    cur.insert({-to(C[i], k + i), C[i]});
    in.insert(C[i]);
  }
  for (int i : to_remove) WriteAdvice(i);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
void Assist(unsigned char *A, int n, int k, int R) {
  vector<int> q;
  set<int> s;
  for (int i = 0; i < k; i++) {
    if (A[i]) q.push_back(i);
    s.insert(i);
  }
  for (int i = 0; i < n; i++) {
    int req = GetRequest();
    if (s.find(req) != s.end()) {
      if (A[k + i]) q.push_back(req); 
      continue;
    }
    PutBack(q.back());
    s.erase(q.back());
    q.pop_back();
    s.insert(req);
    if (A[k + i]) q.push_back(req);
  }
}

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