oj.uz

Submission #103274

# Submission time Handle Problem Language Result Execution time Memory
103274 2019-03-29T12:34:04 Z wxh010910 Last supper (IOI12_supper) C++17
100 / 100
 161 ms 17120 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

void ComputeAdvice(int* C, int N, int K, int M) {
  vector<int> pos(N, -1), nxt(N, N);
  priority_queue<pair<int, int>> q;
  for (int i = 0; i < N; ++i) {
    if (pos[C[i]] != -1) {
      nxt[pos[C[i]]] = i;
    } else if (C[i] < K) {
      q.emplace(i, C[i]);
    }
    pos[C[i]] = i;
  }
  vector<bool> in(N);
  for (int i = 0; i < K; ++i) {
    if (pos[i] == -1) {
      q.emplace(N, i);
    }
    in[i] = true;
  }
  vector<vector<int>> pass(N);
  for (int i = 0; i < N; ++i) {
    if (in[C[i]]) {
      pass[C[i]].push_back(0);
    } else {
      int take = q.top().second;
      q.pop();
      in[C[i]] = true;
      in[take] = false;
      pass[take].push_back(1);
    }
    q.emplace(nxt[i], C[i]);
  }
  vector<int> ptr(N);
  for (int i = 0; i < N + K; ++i) {
    int color = i < K ? i : C[i - K];
    if (ptr[color] == (int) pass[color].size()) {
      WriteAdvice(1);
    } else {
      WriteAdvice(pass[color][ptr[color]++]);
    }
  }
}

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

void Assist(unsigned char* A, int N, int K, int R) {
  vector<bool> in(N);
  queue<int> q;
  for (int i = 0; i < K; ++i) {
    in[i] = true;
    if (A[i]) {
      q.push(i);
    }
  }
  for (int i = 0; i < N; ++i) {
    int c = GetRequest();
    if (!in[c]) {
      in[c] = true;
      in[q.front()] = false;
      PutBack(q.front());
      q.pop();
    }
    if (A[i + K]) {
      q.push(c);
    }
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 644 KB Output is correct
2 Correct 5 ms 908 KB Output is correct
3 Correct 7 ms 932 KB Output is correct
4 Correct 8 ms 1136 KB Output is correct
5 Correct 12 ms 1280 KB Output is correct
6 Correct 13 ms 1280 KB Output is correct
7 Correct 11 ms 1280 KB Output is correct
8 Correct 13 ms 1280 KB Output is correct
9 Correct 8 ms 1280 KB Output is correct
10 Correct 11 ms 1536 KB Output is correct
11 Correct 9 ms 1296 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2048 KB Output is correct
2 Correct 51 ms 7040 KB Output is correct
3 Correct 118 ms 16752 KB Output is correct
4 Correct 129 ms 14064 KB Output is correct
5 Correct 106 ms 14064 KB Output is correct
6 Correct 93 ms 14560 KB Output is correct
7 Correct 93 ms 15072 KB Output is correct
8 Correct 93 ms 14544 KB Output is correct
9 Correct 87 ms 11584 KB Output is correct
10 Correct 120 ms 15520 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 12584 KB Output is correct
2 Correct 112 ms 15192 KB Output is correct
3 Correct 104 ms 15344 KB Output is correct
4 Correct 97 ms 15064 KB Output is correct
5 Correct 100 ms 14320 KB Output is correct
6 Correct 127 ms 15320 KB Output is correct
7 Correct 130 ms 15320 KB Output is correct
8 Correct 122 ms 17120 KB Output is correct
9 Correct 110 ms 14296 KB Output is correct
10 Correct 125 ms 15320 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 8 ms 1536 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 9 ms 1280 KB Output is correct
5 Correct 11 ms 1280 KB Output is correct
6 Correct 10 ms 1280 KB Output is correct
7 Correct 10 ms 1280 KB Output is correct
8 Correct 11 ms 1280 KB Output is correct
9 Correct 10 ms 1280 KB Output is correct
10 Correct 8 ms 1536 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 15072 KB Output is correct - 120000 bits used
2 Correct 106 ms 15320 KB Output is correct - 122000 bits used
3 Correct 132 ms 15320 KB Output is correct - 125000 bits used
4 Correct 145 ms 15320 KB Output is correct - 125000 bits used
5 Correct 134 ms 15320 KB Output is correct - 125000 bits used
6 Correct 132 ms 15320 KB Output is correct - 125000 bits used
7 Correct 161 ms 15216 KB Output is correct - 124828 bits used
8 Correct 120 ms 15584 KB Output is correct - 124910 bits used
9 Correct 129 ms 15320 KB Output is correct - 125000 bits used
10 Correct 141 ms 16864 KB Output is correct - 125000 bits used