oj.uz

Submission #987526

# Submission time Handle Problem Language Result Execution time Memory
987526 2024-05-23T00:39:20 Z huutuan Last supper (IOI12_supper) C++14
100 / 100
 211 ms 146064 KB 
#include "advisor.h"
#include <bits/stdc++.h>

using namespace std;

static const int N=2e5+10;

static queue<int> v[N];
static bool on[N];
static int del[N], nxt[N];
static int add[N];

void ComputeAdvice(int *c, int n, int k, int m){
   int lg=32-__builtin_clz(k);
   for (int i=0; i<n; ++i) v[c[i]].push(i+1);
   for (int i=0; i<n; ++i) v[i].push(n+1);
   set<pair<int, int>, greater<pair<int, int>>> pq;
   for (int i=0; i<=n+k; ++i) nxt[i]=del[i]=n+1;
   for (int i=0; i<k; ++i) pq.emplace(v[i].front(), i), on[i]=1, add[i]=0, nxt[i]=v[i].front();
   for (int t=1; t<=n; ++t){
      int x=c[t-1];
      pq.erase({v[x].front(), x});
      v[x].pop();
      add[x]=t;
      nxt[t+k]=v[x].front();
      if (!on[x]){
         int y=pq.begin()->second; pq.erase(pq.begin());
         if (!add[y]){
            del[y]=t;
         }else{
            del[add[y]+k]=t;
         }
         on[y]=0;
         on[x]=1;
      }
      pq.emplace(v[x].front(), x);
   }
   for (int i=0; i<k; ++i) WriteAdvice(nxt[i]<del[i]);
   for (int i=k+1; i<=n+k; ++i) WriteAdvice(nxt[i]<del[i]);
}

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

using namespace std;

void Assist(unsigned char *a, int n, int k, int r){
   int lg=32-__builtin_clz(k);
   vector<int> v(k);
   iota(v.begin(), v.end(), 0);
   int cur=0;
   set<int> st(v.begin(), v.end());
   vector<int> q;
   for (int i=0; i<k; ++i){
      int y=a[cur++];
      if (!y) q.push_back(i);
   }
   for (int i=0; i<n; ++i){
      int x=GetRequest();
      int y=a[cur++];
      if (!st.count(x)){
         PutBack(q.back()); st.erase(q.back());
         st.insert(x);
         q.pop_back();
      }
      if (!y) q.push_back(x);
   }
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:14:8: warning: unused variable 'lg' [-Wunused-variable]
   14 |    int lg=32-__builtin_clz(k);
      |        ^~

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:7:8: warning: unused variable 'lg' [-Wunused-variable]
    7 |    int lg=32-__builtin_clz(k);
      |        ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 137824 KB Output is correct
2 Correct 81 ms 137792 KB Output is correct
3 Correct 81 ms 137860 KB Output is correct
4 Correct 82 ms 137684 KB Output is correct
5 Correct 91 ms 137888 KB Output is correct
6 Correct 75 ms 137852 KB Output is correct
7 Correct 83 ms 138176 KB Output is correct
8 Correct 109 ms 137996 KB Output is correct
9 Correct 88 ms 138232 KB Output is correct
10 Correct 82 ms 137976 KB Output is correct
11 Correct 85 ms 138008 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 138408 KB Output is correct
2 Correct 121 ms 140200 KB Output is correct
3 Correct 206 ms 146064 KB Output is correct
4 Correct 155 ms 141676 KB Output is correct
5 Correct 149 ms 141660 KB Output is correct
6 Correct 211 ms 142632 KB Output is correct
7 Correct 185 ms 143944 KB Output is correct
8 Correct 174 ms 144232 KB Output is correct
9 Correct 125 ms 141556 KB Output is correct
10 Correct 202 ms 144836 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 143328 KB Output is correct
2 Correct 192 ms 144436 KB Output is correct
3 Correct 206 ms 144552 KB Output is correct
4 Correct 181 ms 144344 KB Output is correct
5 Correct 187 ms 143844 KB Output is correct
6 Correct 208 ms 144444 KB Output is correct
7 Correct 180 ms 144444 KB Output is correct
8 Correct 200 ms 144436 KB Output is correct
9 Correct 159 ms 144276 KB Output is correct
10 Correct 204 ms 144348 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 137948 KB Output is correct
2 Correct 76 ms 137800 KB Output is correct
3 Correct 89 ms 138196 KB Output is correct
4 Correct 88 ms 137948 KB Output is correct
5 Correct 86 ms 137748 KB Output is correct
6 Correct 74 ms 137824 KB Output is correct
7 Correct 88 ms 137976 KB Output is correct
8 Correct 87 ms 137908 KB Output is correct
9 Correct 84 ms 137972 KB Output is correct
10 Correct 105 ms 138240 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 143916 KB Output is correct - 120000 bits used
2 Correct 190 ms 144136 KB Output is correct - 122000 bits used
3 Correct 207 ms 144472 KB Output is correct - 125000 bits used
4 Correct 209 ms 144528 KB Output is correct - 125000 bits used
5 Correct 197 ms 144552 KB Output is correct - 125000 bits used
6 Correct 204 ms 144524 KB Output is correct - 125000 bits used
7 Correct 189 ms 144764 KB Output is correct - 124828 bits used
8 Correct 208 ms 144420 KB Output is correct - 124910 bits used
9 Correct 197 ms 144484 KB Output is correct - 125000 bits used
10 Correct 181 ms 144448 KB Output is correct - 125000 bits used