oj.uz

Submission #1076903

# Submission time Handle Problem Language Result Execution time Memory
1076903 2024-08-26T18:32:56 Z Half Last supper (IOI12_supper) C++17
100 / 100
 199 ms 23412 KB 
#include "advisor.h"
#include <bits/stdc++.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 "assistant.h"
#include <bits/stdc++.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 780 KB Output is correct
2 Correct 1 ms 788 KB Output is correct
3 Correct 2 ms 1048 KB Output is correct
4 Correct 3 ms 1352 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 8 ms 1528 KB Output is correct
7 Correct 5 ms 1632 KB Output is correct
8 Correct 5 ms 1640 KB Output is correct
9 Correct 6 ms 1624 KB Output is correct
10 Correct 6 ms 1892 KB Output is correct
11 Correct 6 ms 1656 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 62 ms 10516 KB Output is correct
3 Correct 164 ms 23412 KB Output is correct
4 Correct 81 ms 18152 KB Output is correct
5 Correct 91 ms 18180 KB Output is correct
6 Correct 128 ms 19484 KB Output is correct
7 Correct 157 ms 21560 KB Output is correct
8 Correct 109 ms 19320 KB Output is correct
9 Correct 75 ms 17928 KB Output is correct
10 Correct 166 ms 22992 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 17668 KB Output is correct
2 Correct 199 ms 22080 KB Output is correct
3 Correct 174 ms 22376 KB Output is correct
4 Correct 169 ms 22304 KB Output is correct
5 Correct 158 ms 21420 KB Output is correct
6 Correct 163 ms 22304 KB Output is correct
7 Correct 166 ms 22336 KB Output is correct
8 Correct 124 ms 22336 KB Output is correct
9 Correct 141 ms 21808 KB Output is correct
10 Correct 178 ms 22332 KB Output is correct

Subtask #4
35.0 / 35.0

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

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 21652 KB Output is correct - 120000 bits used
2 Correct 154 ms 21812 KB Output is correct - 122000 bits used
3 Correct 167 ms 22304 KB Output is correct - 125000 bits used
4 Correct 163 ms 22204 KB Output is correct - 125000 bits used
5 Correct 161 ms 22228 KB Output is correct - 125000 bits used
6 Correct 193 ms 22324 KB Output is correct - 125000 bits used
7 Correct 196 ms 22300 KB Output is correct - 124828 bits used
8 Correct 168 ms 22276 KB Output is correct - 124910 bits used
9 Correct 181 ms 22408 KB Output is correct - 125000 bits used
10 Correct 188 ms 22328 KB Output is correct - 125000 bits used