제출 #1169001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169001		anmattroi	Last supper (IOI12_supper)	C++17	43 / 100	198 ms	11736 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int Lim;

int n;

void insert_number(int x) {
    for (int i = 0; i < Lim; i++) WriteAdvice(x>>i&1);
}

vector<int> nho[maxn];

int bit[maxn];

void upd(int u, int d) {
    for (int i = u; i <= n; i += i & -i) bit[i] += d;
}

int get(int u) {
    int kq = 0;
    for (int i = u; i > 0; i -= i & -i) kq += bit[i];
    return kq;
}

void ComputeAdvice(int *C, int N, int K, int M) {
    Lim = __lg(K)+1; n = N;

    for (int i = 0; i < N; i++) nho[i].emplace_back(INT_MAX);
    for (int i = N-1; i>=0;i--) nho[C[i]].emplace_back(i);


    set<ii> q;
    for (int i = 0; i < K; i++) {
        upd(i+1, 1);
        q.insert(ii{nho[i].back(), i});
    }
    for (int o = 0; o < N; o++) {
        int cur = C[o];
        auto it = q.find(ii{nho[cur].back(), cur});
        if (it != q.end()) {
            q.erase(ii{nho[cur].back(), cur});
            nho[cur].pop_back();
            q.insert(ii{nho[cur].back(), cur});
            continue;
        }

        auto [TIME, COLOR] = *q.rbegin();
        nho[cur].pop_back();
        insert_number(get(COLOR+1));

        upd(COLOR+1, -1);

        q.erase(ii{TIME, COLOR});
        q.insert(ii{nho[cur].back(), cur});

        upd(cur+1, 1);
    }
}

/*
4 2 100
2 0 3 0
*/

assistant

#include "assistant.h"
#include <bits/stdc++.h>
#define maxn 400005
using namespace std;

int _Lim, _n;

int st[4*maxn];

void upd(int u, int d, int r = 1, int lo = 0, int hi = _n-1) {
    if (lo == hi) {
        st[r] = d;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) upd(u, d, r<<1, lo, mid);
    else upd(u, d, r<<1|1, mid+1, hi);
    st[r] = st[r<<1] + st[r<<1|1];
}

int get(int u, int v, int r = 1, int lo = 0, int hi = _n-1) {
    if (u <= lo && hi <= v) return st[r];
    int mid = (lo + hi) >> 1;
    return (u <= mid ? get(u, v, r<<1, lo, mid) : 0) +
           (v  > mid ? get(u, v, r<<1|1, mid+1, hi) : 0);
}

int bfind(int d, int r = 1, int lo = 0, int hi = _n-1) {
    if (lo == hi) return lo;
    int mid = (lo + hi) >> 1, trai = st[r<<1];
    return d > trai ? bfind(d-trai, r<<1|1, mid+1, hi) : bfind(d, r<<1, lo, mid);
}

void Assist(unsigned char *A, int N, int K, int R) {
    _Lim = __lg(K) + 1; _n = N;

    for (int i = 0; i < K; i++)
        upd(i, 1);
    int orz = 0;

    for (int step = 0; step < N; step++) {
        int cur = GetRequest();
        if (get(cur, cur)) continue;
        int num = 0;
        for (int i = orz; i < orz+_Lim; i++)
            num += ((A[i]) << (i-orz));
        orz += _Lim;

        int T = bfind(num);
        PutBack(T);

        upd(T, 0);
        upd(cur, 1);
    }
}

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