oj.uz

Submission #805479

# Submission time Handle Problem Language Result Execution time Memory
805479 2023-08-03T16:59:32 Z raysh07 Last supper (IOI12_supper) C++17
100 / 100
 100 ms 8832 KB 
#include <bits/stdc++.h>
#include "advisor.h"
#define f first
#define s second
 
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 <pair<int, int>, greater <pair<int, int>> > 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;
    }
    
    for(int i=  0; i < n; i++){
          if(used[c[i]] == -1){
         int o = pq.begin()->s;
         
         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]);
}
#include <bits/stdc++.h>
#include "assistant.h"
#define f first
#define s second
 
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 1 ms 512 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 3 ms 660 KB Output is correct
5 Correct 3 ms 804 KB Output is correct
6 Correct 5 ms 804 KB Output is correct
7 Correct 3 ms 872 KB Output is correct
8 Correct 4 ms 932 KB Output is correct
9 Correct 4 ms 924 KB Output is correct
10 Correct 5 ms 968 KB Output is correct
11 Correct 4 ms 936 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1232 KB Output is correct
2 Correct 41 ms 3284 KB Output is correct
3 Correct 93 ms 8832 KB Output is correct
4 Correct 56 ms 4884 KB Output is correct
5 Correct 62 ms 4784 KB Output is correct
6 Correct 78 ms 5676 KB Output is correct
7 Correct 88 ms 7272 KB Output is correct
8 Correct 77 ms 6736 KB Output is correct
9 Correct 51 ms 4764 KB Output is correct
10 Correct 97 ms 8284 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 6376 KB Output is correct
2 Correct 91 ms 7688 KB Output is correct
3 Correct 93 ms 7764 KB Output is correct
4 Correct 94 ms 7904 KB Output is correct
5 Correct 87 ms 7640 KB Output is correct
6 Correct 94 ms 7756 KB Output is correct
7 Correct 98 ms 7932 KB Output is correct
8 Correct 87 ms 7604 KB Output is correct
9 Correct 78 ms 8352 KB Output is correct
10 Correct 92 ms 7884 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 924 KB Output is correct
3 Correct 3 ms 804 KB Output is correct
4 Correct 3 ms 816 KB Output is correct
5 Correct 4 ms 828 KB Output is correct
6 Correct 4 ms 956 KB Output is correct
7 Correct 4 ms 1000 KB Output is correct
8 Correct 4 ms 948 KB Output is correct
9 Correct 5 ms 952 KB Output is correct
10 Correct 6 ms 1280 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 7436 KB Output is correct - 120000 bits used
2 Correct 98 ms 7608 KB Output is correct - 122000 bits used
3 Correct 93 ms 7820 KB Output is correct - 125000 bits used
4 Correct 92 ms 7892 KB Output is correct - 125000 bits used
5 Correct 96 ms 7936 KB Output is correct - 125000 bits used
6 Correct 92 ms 7764 KB Output is correct - 125000 bits used
7 Correct 92 ms 7768 KB Output is correct - 124828 bits used
8 Correct 100 ms 7692 KB Output is correct - 124910 bits used
9 Correct 93 ms 7908 KB Output is correct - 125000 bits used
10 Correct 90 ms 7532 KB Output is correct - 125000 bits used