Submission #789465

#	Time	Username	Problem	Language	Result	Execution time	Memory
789465		Ronin13	Last supper (IOI12_supper)	C++17	100 / 100	115 ms	10132 KiB

advisor

#include <bits/stdc++.h>
#include "advisor.h"
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
void ComputeAdvice(int *c, int n, int k, int m) {
    int ans[n + k];
    vector <int> used(n, -1);
    fill(ans, ans + n + k, 1);
  set <pii, greater <pii> > pq;
    int nx[n + k];
    int last[n];
    fill(nx, nx + n + k, 1e9);
    fill(last, last + n, 1e9);
    for(int i = n - 1; i >= 0; i--){
        nx[i + k] = last[c[i]];
        last[c[i]] = i + k;
    }
    for(int i = k - 1; i >= 0; i--){
        nx[i] = last[i];
        last[i] = i;
        pq.insert({nx[i], i});
        used[i] = i;
    }
    //cout << 1;
    
    for(int i=  0; i < n; i++){
          if(used[c[i]] == -1){
         int o = pq.begin()->s;
       //  cout << nx[o] << ' ';
         
         int vv;
         if(o < k) vv = o;
         else vv = c[o - k];
         used[vv] = -1;
          pq.erase(pq.begin());
          ans[o] = 0;
          }
          pq.erase({i + k, used[c[i]]});
          
          used[c[i]] = i + k;
          pq.insert({nx[i + k], i + k});
      
    }
    for(int i = 0; i < n + k; i++)
      WriteAdvice(ans[i]);
    //cout << 1;
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

void Assist(unsigned char *a, int n, int k, int r) {

       set <int> x, y;
      int cur[k];
      int pos[n];
      for(int i = 0; i < k; i++){
          if(a[i] == 0) y.insert(i);
          x.insert(i);
          cur[i] =i;
          pos[i] = i;
      }
      for(int i = 0; i < n; i++){
          int val = GetRequest();
          if(x.find(val) != x.end()){
              if(a[i + k] == 0) y.insert(pos[val]);
          }
          else{
              int ops = *y.begin();
              y.erase(y.begin());
              PutBack(cur[ops]);
              x.erase(cur[ops]);
              pos[val] = ops;
              cur[ops] = val;
              if(a[i + k] == 0)
                y.insert(ops);
               x.insert(val);
          }
      }
} 

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39