oj.uz

Submission #171109

# Submission time Handle Problem Language Result Execution time Memory
171109 2019-12-27T12:18:51 Z AlexLuchianov Last supper (IOI12_supper) C++14
100 / 100
 397 ms 20240 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{
      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';
  //*/

}

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 984 KB Output is correct
2 Correct 8 ms 852 KB Output is correct
3 Correct 6 ms 1008 KB Output is correct
4 Correct 7 ms 940 KB Output is correct
5 Correct 6 ms 1264 KB Output is correct
6 Correct 11 ms 1264 KB Output is correct
7 Correct 12 ms 1084 KB Output is correct
8 Correct 13 ms 1520 KB Output is correct
9 Correct 13 ms 1264 KB Output is correct
10 Correct 17 ms 1776 KB Output is correct
11 Correct 15 ms 1520 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2232 KB Output is correct
2 Correct 112 ms 5360 KB Output is correct
3 Correct 355 ms 20240 KB Output is correct
4 Correct 172 ms 12264 KB Output is correct
5 Correct 191 ms 12032 KB Output is correct
6 Correct 243 ms 13296 KB Output is correct
7 Correct 329 ms 16032 KB Output is correct
8 Correct 254 ms 17392 KB Output is correct
9 Correct 129 ms 6384 KB Output is correct
10 Correct 346 ms 17904 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 13680 KB Output is correct
2 Correct 326 ms 16880 KB Output is correct
3 Correct 335 ms 16880 KB Output is correct
4 Correct 335 ms 16312 KB Output is correct
5 Correct 301 ms 13552 KB Output is correct
6 Correct 348 ms 17088 KB Output is correct
7 Correct 330 ms 16888 KB Output is correct
8 Correct 307 ms 19640 KB Output is correct
9 Correct 314 ms 13480 KB Output is correct
10 Correct 333 ms 16872 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1324 KB Output is correct
2 Correct 13 ms 1520 KB Output is correct
3 Correct 10 ms 1088 KB Output is correct
4 Correct 10 ms 1264 KB Output is correct
5 Correct 13 ms 1264 KB Output is correct
6 Correct 11 ms 1264 KB Output is correct
7 Correct 15 ms 1520 KB Output is correct
8 Correct 13 ms 1572 KB Output is correct
9 Correct 13 ms 1520 KB Output is correct
10 Correct 17 ms 2032 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 15856 KB Output is correct - 120000 bits used
2 Correct 331 ms 16584 KB Output is correct - 122000 bits used
3 Correct 397 ms 16880 KB Output is correct - 125000 bits used
4 Correct 380 ms 17072 KB Output is correct - 125000 bits used
5 Correct 378 ms 17080 KB Output is correct - 125000 bits used
6 Correct 340 ms 17136 KB Output is correct - 125000 bits used
7 Correct 340 ms 16880 KB Output is correct - 124828 bits used
8 Correct 336 ms 17136 KB Output is correct - 124910 bits used
9 Correct 340 ms 17136 KB Output is correct - 125000 bits used
10 Correct 361 ms 19640 KB Output is correct - 125000 bits used