oj.uz

Submission #171105

# Submission time Handle Problem Language Result Execution time Memory
171105 2019-12-27T11:39:07 Z AlexLuchianov Last supper (IOI12_supper) C++14
0 / 100
 351 ms 19440 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(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';
  //*/

}

#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 1008 KB Output is correct
2 Incorrect 4 ms 884 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 24 ms 2288 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 247 ms 13792 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 Runtime error 8 ms 1148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 16112 KB Output isn't correct - not an optimal way
2 Incorrect 307 ms 16392 KB Output isn't correct - not an optimal way
3 Runtime error 103 ms 13688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 95 ms 13388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 330 ms 17096 KB Output isn't correct - not an optimal way
6 Incorrect 320 ms 17136 KB Output isn't correct - not an optimal way
7 Incorrect 316 ms 16872 KB Output isn't correct - not an optimal way
8 Incorrect 309 ms 16880 KB Output isn't correct - not an optimal way
9 Runtime error 97 ms 13660 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 351 ms 19440 KB Output isn't correct - not an optimal way