제출 #1219774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219774		abczz	최후의 만찬 (IOI12_supper)	C++20	100 / 100	64 ms	8896 KiB

advisor

#include "advisor.h"
#include <iostream>
#include <queue>
#include <vector>
#include <array>
#define ll long long

using namespace std;

priority_queue <array<ll, 2>> pq;
bool B[100000], keep[200000];
ll pv[100000];
vector <ll> color[100000];
void ComputeAdvice(int *C, int N, int K, int M) {
  for (int i=N-1; i>=0; --i) {
    pv[i] = -1;
    B[i] = 0;
    color[C[i]].push_back(i);
  }
  while (!pq.empty()) pq.pop();
  for (int i=0; i<K; ++i) {
    B[i] = 1;
    if (color[i].empty()) pq.push({(ll)1e18, i});
    else pq.push({color[i].back(), i});
  }
  for (int i=0; i<N; ++i) { 
    color[C[i]].pop_back();
    if (B[C[i]]) {
      if (pv[C[i]] != -1) keep[pv[C[i]]] = 1;
      else keep[N+C[i]] = 1;
      pv[C[i]] = i;
      if (color[C[i]].empty()) pq.push({(ll)1e18, C[i]});
      else pq.push({color[C[i]].back(), C[i]});
      continue;
    }
    while (!pq.empty()) {
      auto [w, u] = pq.top();
      pq.pop();
      if (w == (ll)1e18) {
        B[u] = 0;
        break;
      }
      if (color[u].empty() || color[u].back() != w || !B[u]) continue;
      B[u] = 0;
      break;
    }
    B[C[i]] = 1;
    pv[C[i]] = i;
    if (color[C[i]].empty()) pq.push({(ll)1e18, C[i]});
    else pq.push({color[C[i]].back(), C[i]});
  }
  for (int i=0; i<K; ++i) WriteAdvice((ll)keep[N+i]);
  for (int i=0; i<N; ++i) WriteAdvice((ll)keep[i]);
}

assistant

#include "assistant.h"
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

bool C[100000];
vector <ll> V;
void Assist(unsigned char *A, int N, int K, int R) {
  for (int i=0; i<N; ++i) C[i] = 0;
  int j = 0;
  while (j < K) {
    C[j] = 1;
    if (A[j] == 0) V.push_back(j);
    ++j;
  }
  for (int i=0; i<N; ++i) {
    ll u = GetRequest();
    if (C[u]) {
      if (A[j++] == 0) V.push_back(u);
      continue;
    }
    PutBack(V.back());
    C[V.back()] = 0;
    V.pop_back();
    C[u] = 1;
    if (A[j++] == 0) V.push_back(u);
    continue;
  }
}

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