oj.uz

Submission #789465

# Submission time Handle Problem Language Result Execution time Memory
789465 2023-07-21T12:18:00 Z Ronin13 Last supper (IOI12_supper) C++17
100 / 100
 115 ms 10132 KB 
#include <bits/stdc++.h>
#include "advisor.h"
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
void ComputeAdvice(int *c, int n, int k, int m) {
    int ans[n + k];
    vector <int> used(n, -1);
    fill(ans, ans + n + k, 1);
  set <pii, greater <pii> > pq;
    int nx[n + k];
    int last[n];
    fill(nx, nx + n + k, 1e9);
    fill(last, last + n, 1e9);
    for(int i = n - 1; i >= 0; i--){
        nx[i + k] = last[c[i]];
        last[c[i]] = i + k;
    }
    for(int i = k - 1; i >= 0; i--){
        nx[i] = last[i];
        last[i] = i;
        pq.insert({nx[i], i});
        used[i] = i;
    }
    //cout << 1;
    
    for(int i=  0; i < n; i++){
          if(used[c[i]] == -1){
         int o = pq.begin()->s;
       //  cout << nx[o] << ' ';
         
         int vv;
         if(o < k) vv = o;
         else vv = c[o - k];
         used[vv] = -1;
          pq.erase(pq.begin());
          ans[o] = 0;
          }
          pq.erase({i + k, used[c[i]]});
          
          used[c[i]] = i + k;
          pq.insert({nx[i + k], i + k});
      
    }
    for(int i = 0; i < n + k; i++)
      WriteAdvice(ans[i]);
    //cout << 1;
}

#include <bits/stdc++.h>
#include "assistant.h"
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

void Assist(unsigned char *a, int n, int k, int r) {

       set <int> x, y;
      int cur[k];
      int pos[n];
      for(int i = 0; i < k; i++){
          if(a[i] == 0) y.insert(i);
          x.insert(i);
          cur[i] =i;
          pos[i] = i;
      }
      for(int i = 0; i < n; i++){
          int val = GetRequest();
          if(x.find(val) != x.end()){
              if(a[i + k] == 0) y.insert(pos[val]);
          }
          else{
              int ops = *y.begin();
              y.erase(y.begin());
              PutBack(cur[ops]);
              x.erase(cur[ops]);
              pos[val] = ops;
              cur[ops] = val;
              if(a[i + k] == 0)
                y.insert(ops);
               x.insert(val);
          }
      }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 2 ms 520 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 652 KB Output is correct
5 Correct 3 ms 820 KB Output is correct
6 Correct 4 ms 820 KB Output is correct
7 Correct 4 ms 856 KB Output is correct
8 Correct 4 ms 948 KB Output is correct
9 Correct 4 ms 956 KB Output is correct
10 Correct 5 ms 952 KB Output is correct
11 Correct 4 ms 956 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1224 KB Output is correct
2 Correct 39 ms 3856 KB Output is correct
3 Correct 94 ms 10132 KB Output is correct
4 Correct 55 ms 6028 KB Output is correct
5 Correct 62 ms 5952 KB Output is correct
6 Correct 87 ms 6688 KB Output is correct
7 Correct 101 ms 8456 KB Output is correct
8 Correct 86 ms 7692 KB Output is correct
9 Correct 57 ms 5872 KB Output is correct
10 Correct 94 ms 9512 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7040 KB Output is correct
2 Correct 115 ms 8852 KB Output is correct
3 Correct 93 ms 8904 KB Output is correct
4 Correct 101 ms 9080 KB Output is correct
5 Correct 88 ms 8744 KB Output is correct
6 Correct 103 ms 9044 KB Output is correct
7 Correct 93 ms 9072 KB Output is correct
8 Correct 91 ms 8720 KB Output is correct
9 Correct 78 ms 9592 KB Output is correct
10 Correct 95 ms 8992 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 920 KB Output is correct
2 Correct 4 ms 932 KB Output is correct
3 Correct 3 ms 804 KB Output is correct
4 Correct 3 ms 936 KB Output is correct
5 Correct 4 ms 928 KB Output is correct
6 Correct 4 ms 820 KB Output is correct
7 Correct 4 ms 924 KB Output is correct
8 Correct 4 ms 940 KB Output is correct
9 Correct 6 ms 920 KB Output is correct
10 Correct 6 ms 1344 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 8160 KB Output is correct - 120000 bits used
2 Correct 96 ms 8352 KB Output is correct - 122000 bits used
3 Correct 94 ms 8556 KB Output is correct - 125000 bits used
4 Correct 92 ms 8648 KB Output is correct - 125000 bits used
5 Correct 93 ms 7964 KB Output is correct - 125000 bits used
6 Correct 92 ms 8568 KB Output is correct - 125000 bits used
7 Correct 91 ms 7860 KB Output is correct - 124828 bits used
8 Correct 105 ms 7788 KB Output is correct - 124910 bits used
9 Correct 91 ms 7764 KB Output is correct - 125000 bits used
10 Correct 87 ms 8284 KB Output is correct - 125000 bits used