제출 #482694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482694		Haruto810198	최후의 만찬 (IOI12_supper)	C++17	100 / 100	359 ms	32592 KiB

advisor

#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]

const int INF = 2147483647;
//const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

const int MAX = 100010;

vi pos[MAX]; // pos[i] = pos. of color i on scaffold
vi pos_scaff[MAX];
vi res; // replace
vi rem; // remove

vi upds[MAX]; // time, pos[i], val

int nxt_req[MAX], nxt_rem[MAX];

struct Node{
    int sl, sr;
    int cnt, Max, Max_id;
};

Node st[4*MAX];

void build(int cidx, int cl, int cr){
    V.sl = cl;
    V.sr = cr;
    V.cnt = 0;
    V.Max = 0;
    V.Max_id = 0;
    if(cl < cr){
        int mid = (cl + cr) / 2;
        build(cidx*2, cl, mid);
        build(cidx*2+1, mid+1, cr);
    }
}

void modify(int cidx, int pos, int type, int val){
    // type = 1: cnt
    // type = 2: Max
    if(pos < V.sl or V.sr < pos) return;
    if(V.sl == V.sr){
        if(type == 1) V.cnt += val;
        if(type == 2) V.Max = val;
        if(V.cnt >= 1) V.Max_id = pos;
        else V.Max_id = 0;
        return;
    }
    else{
        modify(cidx*2, pos, type, val);
        modify(cidx*2+1, pos, type, val);

        if(LC.cnt >= 1 and RC.cnt >= 1){
            if(LC.Max > RC.Max){
                V.cnt = LC.cnt;
                V.Max = LC.Max;
                V.Max_id = LC.Max_id;
            }
            else{
                V.cnt = RC.cnt;
                V.Max = RC.Max;
                V.Max_id = RC.Max_id;
            }
        }
        else if(LC.cnt >= 1){
            V.cnt = LC.cnt;
            V.Max = LC.Max;
            V.Max_id = LC.Max_id;
        }
        else if(RC.cnt >= 1){
            V.cnt = RC.cnt;
            V.Max = RC.Max;
            V.Max_id = RC.Max_id;
        }
        else{
            V.cnt = 0;
            V.Max = 0;
            V.Max_id = 0;
        }
    }
}

vi query(){
    return {st[1].cnt, st[1].Max, st[1].Max_id};
}

int query2(int cidx, int pos){
    if(pos < V.sl or V.sr < pos){
        return 0;
    }
    else if(V.sl == V.sr){
        return V.cnt;
    }
    else{
        return query2(cidx*2, pos) + query2(cidx*2+1, pos);
    }
}

void ComputeAdvice(int *C, int N, int K, int M){

    FOR(i, 0, K-1, 1){
        pos_scaff[i].pb(i);
    }

    FOR(i, 0, N-1, 1){
        pos[C[i]].pb(i);
    }
    FOR(i, 0, N-1, 1){
        pos[i].pb(INF);

        FOR(j, 0, szof(pos[i]) - 2, 1){
            upds[ pos[i][j] ].pb(i);
        }

        reverse(pos[i].begin(), pos[i].end());
    }

    build(1, 0, N-1);

    FOR(i, 0, K-1, 1){
        modify(1, i, 1, 1);
    }
    FOR(i, 0, N-1, 1){
        modify(1, i, 2, pos[i].back());
    }

    //cerr<<"advisor : "<<endl;

    FOR(i, 0, N-1, 1){

        for(int j : upds[i]){
            pos[j].pop_back();
            modify(1, j, 2, pos[j].back());
        }

        if(query2(1, C[i]) > 0){
            res.pb(K); // K -> do nothing
            rem.pb(-1);
            continue;
        }

        vi ret = query();
        assert(ret[0] > 0);

        // add C[i], remove ret[2], upd t. of C[i]
        modify(1, C[i], 1, 1);
        modify(1, ret[2], 1, -1);
        rem.pb(ret[2]);
        modify(1, C[i], 2, pos[C[i]].back());

        // pos. on scaff
        res.pb(pos_scaff[ret[2]].back());
        pos_scaff[C[i]].pb(pos_scaff[ret[2]].back());
        pos_scaff[ret[2]].pop_back();

    }

    //cerr<<"ok"<<endl;

    //
    FOR(i, 0, N-1, 1){
        nxt_req[i] = INF;
        nxt_rem[i] = INF;
    }

    //cerr<<"ok"<<endl;

    FOR(i, 0, N-1, 1){
        nxt_req[C[i]] = min(nxt_req[C[i]], i);
        if(res[i] != K){
            assert(rem[i] <= N-1);
            nxt_rem[rem[i]] = min(nxt_rem[rem[i]], i);
        }
    }

    //cerr<<"ok"<<endl;

    FOR(i, 0, K-1, 1){
        if(nxt_req[i] < nxt_rem[i]) WriteAdvice(1);
        else WriteAdvice(0);
    }

    //cerr<<"ok"<<endl;

    FOR(i, 0, N-1, 1){
        nxt_rem[i] = INF;
        nxt_req[i] = INF;
    }

    vi owo;

    for(int i = N-1; i >= 0; i--){
        if(nxt_req[C[i]] < nxt_rem[C[i]]) owo.pb(1);
        else owo.pb(0);
        nxt_req[C[i]] = i;
        nxt_rem[rem[i]] = i;
    }

    reverse(owo.begin(), owo.end());
    for(int i : owo){
        WriteAdvice(i);
    }

    //cerr<<"ok"<<endl;

}

assistant

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

//const int INF = 2147483647;
//const int LNF = INF*INF;
//const int MOD = 1000000007;
//const int mod = 998244353;
//const double eps = 1e-12;

//const int MAX = 100010;
set<int> ac, ps, re;

void Assist(unsigned char *A, int N, int K, int R){

    /*
    FOR(i, 0, R-1, 1){
        cerr<<(int)A[i];
    }
    cerr<<endl;
    */

    FOR(i, 0, K-1, 1){
        if(A[i] == 1) ac.insert(i);
        else ps.insert(i);
    }
    FOR(i, K, N-1, 1){
        re.insert(i);
    }

    FOR(j, K, K+N-1, 1){
        int i = j - K;
        // +u, -v

        int u = GetRequest();

        if(re.find(u) == re.end()){
            if(ac.find(u) != ac.end() and A[j] == 0){
                ac.erase(u);
                ps.insert(u);
            }
        }
        else if(A[j] == 1){
            int v = *ps.begin();
            ps.erase(v);
            ac.insert(u);
            re.erase(u);
            re.insert(v);
            PutBack(v);
        }
        else{
            int v = *ps.begin();
            ps.erase(v);
            ps.insert(u);
            re.erase(u);
            re.insert(v);
            PutBack(v);
        }

    }

}

컴파일 시 표준 에러 (stderr) 메시지

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:49:13: warning: unused variable 'i' [-Wunused-variable]
   49 |         int i = j - K;
      |             ^

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