oj.uz

Submission #829660

# Submission time Handle Problem Language Result Execution time Memory
829660 2023-08-18T13:52:30 Z FEDIKUS Last supper (IOI12_supper) C++17
0 / 100
 198 ms 75804 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()) continue;
    auto [kad,ind]=*imam.begin();
    imam.erase(*imam.begin());
    tren.erase(ind);

    addv[prosli[ind]]=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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68032 KB Output is correct
2 Incorrect 31 ms 67848 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 68780 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 74048 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 68336 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 74876 KB Output isn't correct - not an optimal way
2 Incorrect 198 ms 75072 KB Output isn't correct - not an optimal way
3 Incorrect 191 ms 75720 KB Output isn't correct - not an optimal way
4 Incorrect 164 ms 75696 KB Output isn't correct - not an optimal way
5 Incorrect 182 ms 75624 KB Output isn't correct - not an optimal way
6 Incorrect 160 ms 75644 KB Output isn't correct - not an optimal way
7 Incorrect 177 ms 75664 KB Output isn't correct - not an optimal way
8 Incorrect 168 ms 75804 KB Output isn't correct - not an optimal way
9 Incorrect 164 ms 75684 KB Output isn't correct - not an optimal way
10 Correct 146 ms 74972 KB Output is correct - 125000 bits used