Submission #70726

#	Time	Username	Problem	Language	Result	Execution time	Memory
70726		funcsr	Last supper (IOI12_supper)	C++17	100 / 100	577 ms	177696 KiB

advisor

#include "advisor.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int last[100000];
queue<int> G[100000];
bool mark[200000];

void ComputeAdvice(int *A, int N, int K, int M) {
  rep(i, N) G[A[i]].push(i);
  rep(i, N) G[i].push(INF);
  set<int> colors;
  set<P> vs;
  rep(i, K) vs.insert(P(-G[i].front(), i)), last[i] = i, colors.insert(i);
  rep(i, N) {
    P m = P(-G[A[i]].front(), A[i]);
    assert(G[A[i]].front()==i);
    G[A[i]].pop();

    assert(colors.size()==vs.size());
    if (colors.find(A[i]) != colors.end()) {
      mark[last[A[i]]] = true;
      vs.erase(m);
      vs.insert(P(-G[A[i]].front(), A[i]));
    }
    else {
      int c = vs.begin()->_2;
      assert(colors.find(c) != colors.end());
      colors.erase(c);
      vs.erase(vs.begin());
      colors.insert(A[i]);
      vs.insert(P(-G[A[i]].front(), A[i]));
    }
    last[A[i]] = i+K;
  }
  //rep(i, N+K) cout<<mark[i];cout<<"\n";
  rep(i, N+K) WriteAdvice(mark[i]);
}

assistant

#include "assistant.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

void Assist(unsigned char *A, int N, int K, int R) {
  assert(R==N+K);
  set<int> colors;
  queue<int> free;
  set<int> keep;
  rep(i, K) {
    colors.insert(i);
    if (A[i]) keep.insert(i);
    else free.push(i);
  }
  rep(i, N) {
    int req = GetRequest();
    if (colors.find(req) != colors.end()) {
      assert(keep.find(req) != keep.end());
      keep.erase(req);
      if (A[i+K]) keep.insert(req);
      else free.push(req);
    }
    else {
      assert(!free.empty());
      PutBack(free.front());
      colors.erase(free.front());
      free.pop();
      if (A[i+K]) keep.insert(req);
      else free.push(req);
      colors.insert(req);
    }
  }
}

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