oj.uz

Submission #599699

# Submission time Handle Problem Language Result Execution time Memory
599699 2022-07-19T19:10:47 Z Soumya1 Last supper (IOI12_supper) C++17
100 / 100
 223 ms 13816 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
void ComputeAdvice(int *C, int n, int k, int M) {
  vector<int> l[n];
  for (int i = 0; i < k; i++) l[i].push_back(i);
  for (int i = 0; i < n; i++) l[C[i]].push_back(k + i);
  for (int i = 0; i < n; i++) l[i].push_back(n + k + 100);
  set<pair<int, int>> cur;
  set<int> in;
  auto to = [&](int i, int j) {
    return *upper_bound(l[i].begin(), l[i].end(), j);
  };
  auto from = [&](int i, int j) {
    auto it = lower_bound(l[i].begin(), l[i].end(), j);
    return *(--it);
  };
  for (int i = 0; i < k; i++) cur.insert({-to(i, i), i}), in.insert(i);
  vector<int> to_remove(n + k);
  for (int i = 0; i < n; i++) {
    if (in.find(C[i]) != in.end()) {
      cur.erase({-k - i, C[i]});
      cur.insert({-to(C[i], k + i), C[i]});
      continue;
    }
    auto [idx, rem] = *cur.begin();
    idx *= -1;
    to_remove[from(rem, idx)] = 1;
    cur.erase(cur.begin());
    in.erase(rem);
    cur.insert({-to(C[i], k + i), C[i]});
    in.insert(C[i]);
  }
  for (int i : to_remove) WriteAdvice(i);
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
void Assist(unsigned char *A, int n, int k, int R) {
  vector<int> q;
  set<int> s;
  for (int i = 0; i < k; i++) {
    if (A[i]) q.push_back(i);
    s.insert(i);
  }
  for (int i = 0; i < n; i++) {
    int req = GetRequest();
    if (s.find(req) != s.end()) {
      if (A[k + i]) q.push_back(req); 
      continue;
    }
    PutBack(q.back());
    s.erase(q.back());
    q.pop_back();
    s.insert(req);
    if (A[k + i]) q.push_back(req);
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 516 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 3 ms 720 KB Output is correct
4 Correct 3 ms 784 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 6 ms 924 KB Output is correct
7 Correct 6 ms 1048 KB Output is correct
8 Correct 6 ms 1180 KB Output is correct
9 Correct 6 ms 1188 KB Output is correct
10 Correct 8 ms 1312 KB Output is correct
11 Correct 6 ms 1188 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1644 KB Output is correct
2 Correct 83 ms 5224 KB Output is correct
3 Correct 197 ms 13816 KB Output is correct
4 Correct 95 ms 8632 KB Output is correct
5 Correct 129 ms 8676 KB Output is correct
6 Correct 139 ms 9632 KB Output is correct
7 Correct 162 ms 11496 KB Output is correct
8 Correct 165 ms 10916 KB Output is correct
9 Correct 81 ms 9312 KB Output is correct
10 Correct 199 ms 13152 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 9900 KB Output is correct
2 Correct 187 ms 12328 KB Output is correct
3 Correct 186 ms 12312 KB Output is correct
4 Correct 181 ms 12492 KB Output is correct
5 Correct 159 ms 11768 KB Output is correct
6 Correct 193 ms 12420 KB Output is correct
7 Correct 174 ms 12448 KB Output is correct
8 Correct 152 ms 12292 KB Output is correct
9 Correct 163 ms 12684 KB Output is correct
10 Correct 181 ms 12412 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1048 KB Output is correct
2 Correct 8 ms 1180 KB Output is correct
3 Correct 6 ms 932 KB Output is correct
4 Correct 5 ms 924 KB Output is correct
5 Correct 5 ms 932 KB Output is correct
6 Correct 6 ms 924 KB Output is correct
7 Correct 6 ms 1140 KB Output is correct
8 Correct 7 ms 1188 KB Output is correct
9 Correct 7 ms 1200 KB Output is correct
10 Correct 10 ms 1580 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 11708 KB Output is correct - 120000 bits used
2 Correct 182 ms 11844 KB Output is correct - 122000 bits used
3 Correct 177 ms 12476 KB Output is correct - 125000 bits used
4 Correct 188 ms 12332 KB Output is correct - 125000 bits used
5 Correct 198 ms 12484 KB Output is correct - 125000 bits used
6 Correct 182 ms 12540 KB Output is correct - 125000 bits used
7 Correct 175 ms 12324 KB Output is correct - 124828 bits used
8 Correct 179 ms 12312 KB Output is correct - 124910 bits used
9 Correct 223 ms 12444 KB Output is correct - 125000 bits used
10 Correct 182 ms 12336 KB Output is correct - 125000 bits used