oj.uz

Submission #829684

# Submission time Handle Problem Language Result Execution time Memory
829684 2023-08-18T14:05:30 Z FEDIKUS Last supper (IOI12_supper) C++17
100 / 100
 219 ms 80240 KB 
#include "advisor.h"
#include<bits/stdc++.h>

using namespace std;
using pii = pair<int,int>;

const int maxn=1e5+10;

stack<int> occur[maxn];

int n;
set<pair<int,int> > imam;
set<int> tren;
int prosli[maxn];
int addv[2*maxn];

void ComputeAdvice(int *c, int _n, int k, int m) {
  n=_n;
  for(int i=n-1;i>=0;i--) occur[c[i]].push(i);
  for(int i=0;i<k;i++){
    int kad=n+1;
    if(!occur[i].empty()) kad=occur[i].top();
    imam.emplace(pii(-kad,i));
    tren.emplace(i);
  }
  for(int i=0;i<k;i++) prosli[i]=i;
  for(int i=0;i<n+k;i++) addv[i]=1;
  for(int i=0;i<n;i++){

    occur[c[i]].pop();
    prosli[c[i]]=k+i;

    if(tren.find(c[i])==tren.end()){      
      auto [kad,ind]=*imam.begin();
      imam.erase(*imam.begin());
      tren.erase(ind);

      addv[prosli[ind]]=0;
    }
    
    int kad=0;
    tren.emplace(c[i]);
    if(occur[c[i]].empty()) kad=n+1;
    else kad=occur[c[i]].top();
    imam.emplace(pii(-kad,c[i]));
  }

  #ifdef DEBUG
  for(int i=0;i<n+k;i++) cout<<addv[i];
  cout<<"\n";
  #endif 

  for(int i=0;i<n+k;i++) WriteAdvice(addv[i]);
}

#include "assistant.h"
#include<bits/stdc++.h>

using namespace std;

void Assist(unsigned char *a, int n, int k, int r) {
  set<int> polumrtvi;
  for(int i=0;i<k;i++) if(a[i]==0) polumrtvi.emplace(i);
  set<int> tren;
  for(int i=0;i<k;i++) tren.emplace(i);
  for(int i=0;i<n;i++){
    int req=GetRequest();
    if(tren.find(req)==tren.end()){
      
      assert(!polumrtvi.empty());
      assert(!tren.empty());

      PutBack(*polumrtvi.begin());
      tren.erase(*polumrtvi.begin());
      polumrtvi.erase(polumrtvi.begin());
    }
    tren.emplace(req);
    if(a[i+k]==0) polumrtvi.emplace(req);
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 67944 KB Output is correct
2 Correct 31 ms 68040 KB Output is correct
3 Correct 37 ms 68268 KB Output is correct
4 Correct 34 ms 68112 KB Output is correct
5 Correct 34 ms 68168 KB Output is correct
6 Correct 44 ms 68092 KB Output is correct
7 Correct 36 ms 68524 KB Output is correct
8 Correct 37 ms 68384 KB Output is correct
9 Correct 37 ms 68284 KB Output is correct
10 Correct 37 ms 68476 KB Output is correct
11 Correct 37 ms 68564 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 68988 KB Output is correct
2 Correct 93 ms 72156 KB Output is correct
3 Correct 189 ms 79604 KB Output is correct
4 Correct 112 ms 72356 KB Output is correct
5 Correct 141 ms 72740 KB Output is correct
6 Correct 149 ms 74448 KB Output is correct
7 Correct 168 ms 77736 KB Output is correct
8 Correct 139 ms 76288 KB Output is correct
9 Correct 98 ms 72356 KB Output is correct
10 Correct 219 ms 79836 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 75860 KB Output is correct
2 Correct 186 ms 78576 KB Output is correct
3 Correct 179 ms 78888 KB Output is correct
4 Correct 182 ms 79048 KB Output is correct
5 Correct 166 ms 78920 KB Output is correct
6 Correct 209 ms 78860 KB Output is correct
7 Correct 181 ms 79100 KB Output is correct
8 Correct 156 ms 77200 KB Output is correct
9 Correct 195 ms 80240 KB Output is correct
10 Correct 184 ms 79104 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 68348 KB Output is correct
2 Correct 38 ms 68524 KB Output is correct
3 Correct 35 ms 68208 KB Output is correct
4 Correct 44 ms 68108 KB Output is correct
5 Correct 40 ms 68164 KB Output is correct
6 Correct 43 ms 68364 KB Output is correct
7 Correct 38 ms 68324 KB Output is correct
8 Correct 38 ms 68496 KB Output is correct
9 Correct 39 ms 68520 KB Output is correct
10 Correct 39 ms 69076 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 76996 KB Output is correct - 120000 bits used
2 Correct 181 ms 77340 KB Output is correct - 122000 bits used
3 Correct 181 ms 77980 KB Output is correct - 125000 bits used
4 Correct 181 ms 78024 KB Output is correct - 125000 bits used
5 Correct 185 ms 78024 KB Output is correct - 125000 bits used
6 Correct 179 ms 77964 KB Output is correct - 125000 bits used
7 Correct 196 ms 78116 KB Output is correct - 124828 bits used
8 Correct 186 ms 77828 KB Output is correct - 124910 bits used
9 Correct 211 ms 78040 KB Output is correct - 125000 bits used
10 Correct 164 ms 76236 KB Output is correct - 125000 bits used