Submission #171109

#	Time	Username	Problem	Language	Result	Execution time	Memory
171109		AlexLuchianov	Last supper (IOI12_supper)	C++14	100 / 100	397 ms	20240 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{
      if(nextmet != a.nextmet)
        return nextmet < a.nextmet;
      else
        return val < a.val;
    }
  };
  std::map<int,int> frec;
  int nextright[1 + nmax] = {0};
  int sol[1 + nmax] = {0};
  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(frec.find(i) != frec.end())
      pq.insert({i, frec[i]});
    else
      pq.insert({i, N});
    active[i] = i;
  }

  int rests = 0, steps = 0;

  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}));
      rests++;
    } else {
      Number pqtop = *pq.rbegin();
      active.erase(pqtop.val);
      pq.erase(pqtop);
      steps++;
    }
    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);
  }

  int rests2 = 0;

  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);
    } else {
      rests2++;
    }
    if(A[K + i] == 0)
      q.push(req);
  }
}

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