oj.uz

Submission #1078117

# Submission time Handle Problem Language Result Execution time Memory
1078117 2024-08-27T12:52:39 Z Pbezz Last supper (IOI12_supper) C++17
100 / 100
 170 ms 23380 KB 
#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
 
void ComputeAdvice(int *C, int n, int k, int m) {
  int inf = 2*n;
  set<int> cur;
  set<pair<int, int>> pri;
  vector<set<int>> nxt(n);
  for(int i = 0; i < n; ++i){
    nxt[C[i]].insert(i);
  }
  for(int i = 0; i < n; ++i){
    nxt[i].insert(inf);
  }
  for(int i = 0; i < k; ++i){
    cur.insert(i);
    pri.insert({-*nxt[i].begin(),i});
  }
  vector<int> rem(n);
  for(int i = 0; i < n; ++i){
    /*for(auto[x, y] : pri)
      printf("%i %i", x, y);
    printf("\n");*/
    int c = C[i];
    if(cur.find(c) != cur.end()){
      rem[i] = -1;
      pri.erase({-*nxt[c].begin(),c});
      nxt[c].erase(nxt[c].begin());
      pri.insert({-*nxt[c].begin(),c});
    }else{
      auto[x, cr] = *pri.begin();
      rem[i] = cr;
      pri.erase(pri.begin());
      cur.erase(cr);
      nxt[c].erase(nxt[c].begin());
      pri.insert({-*nxt[c].begin(),c});
      cur.insert(c);
    }
  }
  /*for(int r : rem)
    printf("%i ", r);
  printf("\n");*/
  vector<int> lst(n, -1);
  vector<unsigned char> sol(n+k, 0);
  for(int i = 0; i < k; ++i){
    lst[i] = i;
  }
  for(int i = 0; i < n; ++i){
    int c = C[i];
    int r = rem[i];
    if(r == -1){
      sol[lst[c]] = 1;
    }else{
      sol[lst[r]] = 0;
    }
    lst[c] = i+k;
  }
  for(unsigned char bit : sol){
    WriteAdvice(bit);
  }
  /*for(unsigned char c : sol)
    printf("%i", c);
  printf("\n");*/
}
 
#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
 
void Assist(unsigned char *A, int n, int k, int r) {
 
  int i;
  set<pair<unsigned char, int>> shelf;
  for(i = 0; i < k; i++){
    shelf.insert({A[i], i});
  }
  for (i = 0; i < n; i++) {
    int c = GetRequest();
    if(shelf.find({1, c}) != shelf.end()){
      shelf.erase({1, c});
      shelf.insert({A[i+k], c});
      continue;
    }
    PutBack(shelf.begin()->second);
    shelf.erase(shelf.begin());
    shelf.insert({A[i+k], c});
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 796 KB Output is correct
2 Correct 0 ms 784 KB Output is correct
3 Correct 2 ms 1048 KB Output is correct
4 Correct 3 ms 1352 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 4 ms 1628 KB Output is correct
7 Correct 6 ms 1632 KB Output is correct
8 Correct 5 ms 1640 KB Output is correct
9 Correct 5 ms 1620 KB Output is correct
10 Correct 6 ms 1880 KB Output is correct
11 Correct 7 ms 1648 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2708 KB Output is correct
2 Correct 60 ms 10420 KB Output is correct
3 Correct 166 ms 23380 KB Output is correct
4 Correct 73 ms 18168 KB Output is correct
5 Correct 86 ms 18184 KB Output is correct
6 Correct 114 ms 19480 KB Output is correct
7 Correct 150 ms 21556 KB Output is correct
8 Correct 117 ms 19308 KB Output is correct
9 Correct 81 ms 17924 KB Output is correct
10 Correct 170 ms 23288 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17696 KB Output is correct
2 Correct 158 ms 22168 KB Output is correct
3 Correct 165 ms 22428 KB Output is correct
4 Correct 159 ms 22296 KB Output is correct
5 Correct 152 ms 21396 KB Output is correct
6 Correct 158 ms 22416 KB Output is correct
7 Correct 157 ms 22580 KB Output is correct
8 Correct 129 ms 22300 KB Output is correct
9 Correct 137 ms 22040 KB Output is correct
10 Correct 159 ms 22332 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1620 KB Output is correct
2 Correct 4 ms 1636 KB Output is correct
3 Correct 4 ms 1624 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 5 ms 1632 KB Output is correct
6 Correct 4 ms 1736 KB Output is correct
7 Correct 6 ms 1632 KB Output is correct
8 Correct 6 ms 1652 KB Output is correct
9 Correct 6 ms 1636 KB Output is correct
10 Correct 8 ms 2156 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 21584 KB Output is correct - 120000 bits used
2 Correct 162 ms 21816 KB Output is correct - 122000 bits used
3 Correct 158 ms 22396 KB Output is correct - 125000 bits used
4 Correct 164 ms 22420 KB Output is correct - 125000 bits used
5 Correct 167 ms 22300 KB Output is correct - 125000 bits used
6 Correct 157 ms 22328 KB Output is correct - 125000 bits used
7 Correct 161 ms 22412 KB Output is correct - 124828 bits used
8 Correct 159 ms 22336 KB Output is correct - 124910 bits used
9 Correct 162 ms 22332 KB Output is correct - 125000 bits used
10 Correct 134 ms 22320 KB Output is correct - 125000 bits used