oj.uz

Submission #171106

# Submission time Handle Problem Language Result Execution time Memory
171106 2019-12-27T11:51:37 Z AlexLuchianov Last supper (IOI12_supper) C++14
0 / 100
 307 ms 18416 KB 
#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(frec.find(i) != frec.end())
      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';
  //*/

}

#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 764 KB Output is correct
2 Incorrect 4 ms 896 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 2032 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 12016 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1264 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 13984 KB Output isn't correct - not an optimal way
2 Incorrect 290 ms 14320 KB Output isn't correct - not an optimal way
3 Incorrect 302 ms 14776 KB Output isn't correct - not an optimal way
4 Incorrect 305 ms 14832 KB Output isn't correct - not an optimal way
5 Incorrect 303 ms 15088 KB Output isn't correct - not an optimal way
6 Incorrect 307 ms 14832 KB Output isn't correct - not an optimal way
7 Incorrect 293 ms 15088 KB Output isn't correct - not an optimal way
8 Incorrect 294 ms 14832 KB Output isn't correct - not an optimal way
9 Incorrect 290 ms 14776 KB Output isn't correct - not an optimal way
10 Incorrect 292 ms 18416 KB Output isn't correct - not an optimal way