oj.uz

Submission #764747

# Submission time Handle Problem Language Result Execution time Memory
764747 2023-06-24T03:01:46 Z ngrace Last supper (IOI12_supper) C++14
43 / 100
 185 ms 11100 KB 
#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

void ComputeAdvice(int *C, int N, int K, int M) {
  int sik = 0;
  for(int i=0; i<32; i++){
    if(K & (1<<i)) sik = i+1;
  }

  v<int> lastpos(N,N+1);
  v<int> nextpos(N);
  v<int> nextposk(K,N+1);
  for(int i=N-1; i>=0; i--){
    if(C[i]<K) nextposk[C[i]] = i;
    nextpos[i] = lastpos[C[i]];
    lastpos[C[i]] = i;
  }

  v<int> scaff(N,-1);
  priority_queue<ii> pq;
  for(int i=0; i<K; i++){
    scaff[i]=i;
    pq.push({nextposk[i], i});
  }

  for(int i=0; i<N; i++){
    int req = C[i];
    if(scaff[req]==-1){
      int rem = pq.top().se;
      pq.pop();
      int k = scaff[rem];
      scaff[req] = k;
      pq.push({nextpos[i], req});
      scaff[rem] = -1;
      
      for(int b=0; b<sik; b++) WriteAdvice((bool)(k & (1<<b)));
    } else{
      pq.push({nextpos[i], req});
    }
  }

}

#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

void Assist(unsigned char *A, int N, int K, int R) {
  int sik = 0;
  for(int i=0; i<32; i++){
    if(K & (1<<i)) sik = i+1;
  }

  v<int> scaff(N, -1);
  v<int> revscaff(K, -1);
  for(int i=0; i<K; i++){
    scaff[i]=i;
    revscaff[i]=i;
  }

  int aind=0;
  for(int i=0; i<N; i++){
    int req = GetRequest();
    if(scaff[req]==-1){
      int k=0;
      for(int j=0; j<sik; j++){
        if(A[aind]==1) k |= (1<<j);
        aind++;
      }
      int rem = revscaff[k];
      PutBack(rem);
      scaff[rem]=-1;
      scaff[req]=k;
      revscaff[k]=req;
    }
  }

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 508 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 680 KB Output is correct
5 Correct 3 ms 820 KB Output is correct
6 Correct 6 ms 1008 KB Output is correct
7 Correct 3 ms 944 KB Output is correct
8 Correct 7 ms 1020 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 5 ms 1108 KB Output is correct
11 Correct 7 ms 1088 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1352 KB Output is correct
2 Correct 52 ms 4068 KB Output is correct
3 Correct 163 ms 10128 KB Output is correct
4 Correct 107 ms 7580 KB Output is correct
5 Correct 177 ms 9716 KB Output is correct
6 Correct 175 ms 9732 KB Output is correct
7 Correct 144 ms 9116 KB Output is correct
8 Correct 151 ms 9336 KB Output is correct
9 Correct 82 ms 6372 KB Output is correct
10 Correct 126 ms 8692 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 6324 KB Output is correct
2 Correct 132 ms 8796 KB Output is correct
3 Correct 139 ms 8844 KB Output is correct
4 Correct 122 ms 8464 KB Output is correct
5 Correct 95 ms 7764 KB Output is correct
6 Correct 145 ms 8748 KB Output is correct
7 Correct 131 ms 8796 KB Output is correct
8 Correct 185 ms 11100 KB Output is correct
9 Correct 100 ms 7608 KB Output is correct
10 Correct 132 ms 8908 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 636 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 7920 KB Output is partially correct - 772365 bits used
2 Correct 140 ms 7672 KB Output is partially correct - 742095 bits used
3 Correct 146 ms 7556 KB Output is partially correct - 712470 bits used
4 Correct 130 ms 7660 KB Output is partially correct - 712005 bits used
5 Correct 140 ms 7652 KB Output is partially correct - 710610 bits used
6 Correct 132 ms 7588 KB Output is partially correct - 712155 bits used
7 Correct 135 ms 7656 KB Output is partially correct - 711090 bits used
8 Correct 130 ms 7672 KB Output is partially correct - 713340 bits used
9 Correct 131 ms 7636 KB Output is partially correct - 712830 bits used
10 Correct 185 ms 9888 KB Output is partially correct - 1117620 bits used