oj.uz

Submission #373497

# Submission time Handle Problem Language Result Execution time Memory
373497 2021-03-04T20:57:43 Z WLZ Last supper (IOI12_supper) C++14
100 / 100
 157 ms 9240 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

void ComputeAdvice(int *C, int N, int K, int M) {
  vector<int> last(N, INF), next(N, INF), in(N, -1), ans(N + K, 0);
  for (int i = N - 1; i >= 0; i--) {
    next[i] = last[C[i]];
    last[C[i]] = i;
  }
  set< pair<int, int> > st;
  for (int i = 0; i < K; i++) {
    st.insert({last[i], i});
    in[i] = i;
  }
  for (int i = 0; i < N; i++) {
    if (in[C[i]] == -1) {
      auto p = *st.rbegin();
      in[p.second] = -1;
      st.erase(p);
      st.insert({next[i], C[i]});
      in[C[i]] = K + i;
    } else {
      ans[in[C[i]]] = 1;
      st.erase({i, C[i]});
      st.insert({next[i], C[i]});
      in[C[i]] = K + i;
    }
  }
  for (int i = 0; i < N + K; i++) WriteAdvice(ans[i]);
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
  vector< set<int> > v(2);
  vector<int> in(N, -1);
  for (int i = 0; i < K; i++) {
    v[A[i]].insert(i);
    in[i] = A[i];
  }
  for (int i = 0; i < N; i++) {
    int x = GetRequest();
    if (in[x] == -1) {
      auto y = *v[0].begin();
      PutBack(y);
      v[in[y]].erase(y);
      in[y] = -1;
      in[x] = A[K + i];
      v[in[x]].insert(x);
    } else {
      v[in[x]].erase(x);
      in[x] = A[K + i];
      v[in[x]].insert(x);
    }
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1020 KB Output is correct
2 Correct 1 ms 1144 KB Output is correct
3 Correct 2 ms 880 KB Output is correct
4 Correct 3 ms 792 KB Output is correct
5 Correct 5 ms 1136 KB Output is correct
6 Correct 5 ms 988 KB Output is correct
7 Correct 7 ms 944 KB Output is correct
8 Correct 9 ms 1136 KB Output is correct
9 Correct 5 ms 944 KB Output is correct
10 Correct 7 ms 1360 KB Output is correct
11 Correct 8 ms 1200 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1840 KB Output is correct
2 Correct 58 ms 3824 KB Output is correct
3 Correct 140 ms 9240 KB Output is correct
4 Correct 73 ms 5824 KB Output is correct
5 Correct 82 ms 6008 KB Output is correct
6 Correct 106 ms 6356 KB Output is correct
7 Correct 157 ms 7876 KB Output is correct
8 Correct 107 ms 7600 KB Output is correct
9 Correct 71 ms 5684 KB Output is correct
10 Correct 152 ms 9020 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 6916 KB Output is correct
2 Correct 149 ms 8408 KB Output is correct
3 Correct 143 ms 8188 KB Output is correct
4 Correct 148 ms 8388 KB Output is correct
5 Correct 147 ms 7872 KB Output is correct
6 Correct 142 ms 8412 KB Output is correct
7 Correct 144 ms 8188 KB Output is correct
8 Correct 122 ms 8380 KB Output is correct
9 Correct 138 ms 8188 KB Output is correct
10 Correct 146 ms 8372 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1064 KB Output is correct
2 Correct 5 ms 1072 KB Output is correct
3 Correct 5 ms 1072 KB Output is correct
4 Correct 5 ms 1072 KB Output is correct
5 Correct 6 ms 944 KB Output is correct
6 Correct 6 ms 1564 KB Output is correct
7 Correct 7 ms 1076 KB Output is correct
8 Correct 7 ms 1072 KB Output is correct
9 Correct 7 ms 1200 KB Output is correct
10 Correct 9 ms 1688 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 7864 KB Output is correct - 120000 bits used
2 Correct 141 ms 8272 KB Output is correct - 122000 bits used
3 Correct 145 ms 8376 KB Output is correct - 125000 bits used
4 Correct 145 ms 8340 KB Output is correct - 125000 bits used
5 Correct 142 ms 8188 KB Output is correct - 125000 bits used
6 Correct 155 ms 8188 KB Output is correct - 125000 bits used
7 Correct 144 ms 8360 KB Output is correct - 124828 bits used
8 Correct 147 ms 8188 KB Output is correct - 124910 bits used
9 Correct 144 ms 8500 KB Output is correct - 125000 bits used
10 Correct 118 ms 8380 KB Output is correct - 125000 bits used