oj.uz

답안 #988809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
988809 2024-05-26T09:38:17 Z Ariadna 최후의 만찬 (IOI12_supper) C++14
0 / 100
 17 ms 5212 KB 
#include "advisor.h"
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

struct Segtree {
    int n;
    vector<pair<int, int>> st;

    Segtree(const vector<int>& a) {
        n = a.size();
        st = vector<pair<int, int>>(4*n);
        build(1, 0, n-1, a);
    }

    void build(int p, int l, int r, const vector<int>& a) {
        if (l == r) st[p] = {a[l], l};
        else {
            int m = (l+r)/2;
            build(2*p, l, m, a);
            build(2*p+1, m+1, r, a);
            if (st[2*p] > st[2*p+1]) st[p] = st[2*p];
            else st[p] = st[2*p+1];
        }
    }

    void change(int p, int l, int r, int i, int v) {
        if (l == r) st[p] = {v, i};
        else {
            int m = (l+r)/2;
            if (i <= m) change(2*p, l, m, i, v);
            else change(2*p+1, m+1, r, i, v);
            if (st[2*p] > st[2*p+1]) st[p] = st[2*p];
            else st[p] = st[2*p+1];
        }
    }

    pair<int, int> Max(int p, int l, int r, int i, int j) {
        if (i > j) return {0, -1};
        if (i == l && j == r) return st[p];
        int m = (l+r)/2;
        pair<int, int> a = Max(2*p, l, m, i, min(m, j));
        pair<int, int> b = Max(2*p+1, m+1, r, max(i, m+1), j);
        if (a.first > b.first) return a;
        return b;
    }

    void change(int i, int v) { change(1, 0, n-1, i, v); }
    int idx() { return Max(1, 0, n-1, 0, n-1).second; }
};

vector<int> LeonardoStrategy(int *C, int N, int K) {
    vector<int> last_pos(N, N);
    vector<int> next_pos(N);

    for (int i = N-1; i >= 0; --i) {
        next_pos[i] = last_pos[C[i]]; 
        last_pos[C[i]] = i; 
    }

    vector<int> pos_on_scaffold(N, -1);
    for (int i = 0; i < K; ++i) pos_on_scaffold[i] = i;

    vector<int> scaffold(K);
    vector<int> next(K);
    for (int i = 0; i < K; ++i) {
        next[i] = last_pos[i];
        scaffold[i] = i;
    }
    Segtree Scaffold(next);
    
    vector<int> optimal_strategy;
    for (int i = 0; i < N; ++i) {
        if (pos_on_scaffold[C[i]] != -1) continue;
        else {
            int idx = Scaffold.idx();
            optimal_strategy.pb(idx);
            Scaffold.change(idx, next_pos[i]);
            pos_on_scaffold[scaffold[idx]] = -1;
            pos_on_scaffold[C[i]] = idx;
            scaffold[idx] = C[i];
        }
    }

    return optimal_strategy;
}

void ComputeAdvice(int *C, int N, int K, int M) {
    vector<int> optimal_strategy = LeonardoStrategy(C, N, K);
    int log_k = 0;
    while ((1<<(log_k+1) <= K)) ++log_k;

    for (int i : optimal_strategy) {
        for (int j = log_k; j >= 0; --j) {
            WriteAdvice(i&(1<<j));
        }
    }
}
#include "assistant.h"
#include <bits/stdc++.h>

using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
    vector<int> scaffold(K);
    vector<int> pos_on_scaffold(N, -1);
    for (int i = 0; i < K; ++i) {
        scaffold[i] = i;
        pos_on_scaffold[i] = i;
    }
    int log_k = 0;
    while (1<<(log_k+1) <= K) ++log_k;
    int j = 0;
    for (int i = 0; i < N; ++i) {
        int c = GetRequest();
        if (pos_on_scaffold[c] != -1) continue;

        int idx = 0;
        for (int i = log_k; i >= 0; --i) {
            idx |= (1<<i)*A[j];
          	++j;
        }

        PutBack(scaffold[idx]);
        pos_on_scaffold[scaffold[idx]] = -1;
        scaffold[idx] = c;
        pos_on_scaffold[c] = idx;

    }
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 784 KB Output is correct
2 Incorrect 0 ms 784 KB Error - advice must be 0 or 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1108 KB Error - advice must be 0 or 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 4208 KB Error - advice must be 0 or 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 800 KB Error - advice must be 0 or 1
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 4840 KB Error - advice must be 0 or 1
2 Incorrect 17 ms 4728 KB Error - advice must be 0 or 1
3 Incorrect 12 ms 4964 KB Error - advice must be 0 or 1
4 Incorrect 12 ms 4960 KB Error - advice must be 0 or 1
5 Incorrect 16 ms 4876 KB Error - advice must be 0 or 1
6 Incorrect 13 ms 4848 KB Error - advice must be 0 or 1
7 Incorrect 14 ms 4856 KB Error - advice must be 0 or 1
8 Incorrect 12 ms 4960 KB Error - advice must be 0 or 1
9 Incorrect 13 ms 5212 KB Error - advice must be 0 or 1
10 Incorrect 12 ms 5084 KB Error - advice must be 0 or 1