fork download
copy 
  1. #include "advisor.h"
  2. #include <queue>
  3. using namespace std;
  4.  
  5. #define MAXN 100005
  6. typedef pair<int,int> pii;
  7.  
  8. static int C[MAXN];
  9. static int in_scaffold[MAXN],recent[MAXN],next_[MAXN],first_active[MAXN],request_active[MAXN],request_num[MAXN];
  10. static priority_queue<pii> que;
  11.  
  12. void ComputeAdvice(int *arr, int N, int K, int M)
  13. {
  14.     int i,k;
  15.     for (i=0;i<N;i++) C[i+1] = arr[i]+1;
  16.     for (i=1;i<=N;i++) next_[i] = 1e9;
  17.     for (i=N;i;i--){
  18.         recent[i] = next_[C[i]];
  19.         next_[C[i]] = i;
  20.     }
  21.     for (i=1;i<=K;i++) in_scaffold[i] = 1, que.push(pii(next_[i],i));
  22.     for (i=1;i<=K;i++) first_active[i] = 0;
  23.     for (i=1;i<=N;i++) request_active[i] = 0;
  24.     for (i=1;i<=N;i++){
  25.         if (in_scaffold[C[i]]){
  26.             if (request_num[C[i]]) request_active[request_num[C[i]]] = 1;
  27.             else first_active[C[i]] = 1;
  28.             request_num[C[i]] = i;
  29.             que.push(pii(recent[i],C[i]));
  30.             continue;
  31.         }
  32.         k = que.top().second; que.pop();
  33.         in_scaffold[C[i]] = 1; in_scaffold[k] = 0;
  34.         request_num[C[i]] = i;
  35.         que.push(pii(recent[i],C[i]));
  36.     }
  37.     for (i=1;i<=K;i++) WriteAdvice(first_active[i]);
  38.     for (i=1;i<=N;i++) WriteAdvice(request_active[i]);
  39. }
  40.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1gTg6v
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!