Submission #171105

#	Time	Username	Problem	Language	Result	Execution time	Memory
171105		AlexLuchianov	최후의 만찬 (IOI12_supper)	C++14	0 / 100	351 ms	19440 KiB

advisor

#include "advisor.h"
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <set>

namespace Advisor{
  int const nmax = 200000;

  struct Number {
    int val;
    int nextmet;
    bool operator < (Number const &a) const{
      return nextmet < a.nextmet;
    }
  };
  std::map<int,int> frec;
  int nextright[1 + nmax];
  int sol[1 + nmax];
  std::map<int,int> active;
}
using namespace Advisor;

void ComputeAdvice(int *C, int N, int K, int M) {
  for(int i = N - 1; 0 <= i; i--){
    if(0 < frec[C[i]] )
      nextright[i] = frec[C[i]];
    else
      nextright[i] = N;
    frec[C[i]] = i;
  }

  std::set<Number> pq;

  for(int i = 0; i < K; i++) {
    if(0 < frec[i])
      pq.insert({i, frec[i]});
    else
      pq.insert({i, N});
    active[i] = i;
  }

  for(int i = 0; i < N; i++){
    if(active.find(C[i]) != active.end()) {
      sol[active[C[i]]] = 1;
      active.erase(C[i]);
      pq.erase(pq.find({C[i], i}));
    } else {
      Number pqtop = *pq.rbegin();
      active.erase(pqtop.val);
      pq.erase(pqtop);
    }
    pq.insert({C[i], nextright[i]});
    active.insert({C[i], K + i});
  }

  for(int i = 0; i < K + N; i++)
    WriteAdvice(sol[i]);
  /*
  std::cout << "Advice:\n";
  for(int i = 0; i < K + N; i++)
    std::cout << sol[i];
  std::cout << '\n';
  //*/

}

assistant

#include "assistant.h"
#include <vector>
#include <queue>
#include <set>
#include <iostream>

namespace asdf{
  std::set<int> active;
}
using namespace asdf;

void Assist(unsigned char *A, int N, int K, int R) {
  for(int i = 0; i < K; i++)
    active.insert(i);
  int i;
  std::queue<int> q;
  for(int i = 0; i < K; i++) {
    if(A[i] == 0)
      q.push(i);
    active.insert(i);
  }

  for (i = 0; i < N; i++) {
    int req = GetRequest();
    //std::cout << i << " " << req << " " << q.size() << '\n';
    if(active.find(req) == active.end()) {
      PutBack(q.front());
      active.erase(q.front());
      q.pop();
      active.insert(req);
    }
    if(A[K + i] == 0) {
      q.push(req);
    }
  }
}

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