Submission #481889

#	Time	Username	Problem	Language	Result	Execution time	Memory
481889		Haruto810198	Last supper (IOI12_supper)	C++17	34 / 100	478 ms	35196 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; // the sequence A

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

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){
    //cerr<<"query2 "<<cidx<<", "<<pos<<endl;
    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());
        }
        /*
        cerr<<"request "<<C[i]<<endl;

        cerr<<"exist : ";
        FOR(j, 0, N-1, 1){
            if(query2(1, j) > 0) cerr<<j<<" ";
        }
        cerr<<endl;

        cerr<<"time : ";
        FOR(j, 0, N-1, 1){
            if(pos[j].back() < INF) cerr<<pos[j].back()<<" ";
            else cerr<<"- ";
        }
        cerr<<endl;
        */

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

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

        // add C[i], remove ret[2], upd t. of C[i]
        modify(1, C[i], 1, 1);
        modify(1, ret[2], 1, -1);
        //pos[C[i]].pop_back();
        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<<"P "<<res.back()<<endl;
    }

    //cerr<<"str : ";

    int sz = __lg(K + 1);
    if((1<<sz) < K + 1) sz++;
    for(int i : res){
        FOR(j, 0, sz-1, 1){
            if(i & (1<<j)) WriteAdvice(1);
            else WriteAdvice(0);
            //if(i & (1<<j)) cerr<<1;
            //else cerr<<0;
        }
    }

    //cerr<<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;
int col[100010];

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

    FOR(i, 0, K-1, 1){
        col[i] = i;
    }

    int sz = R / N;
    FOR(i, 0, N-1, 1){
        int newcol = GetRequest();

        int val = 0;
        FOR(j, 0, sz-1, 1){
            if(A[i*sz + j] == 1) val += (1<<j);
        }

        //cerr<<"val = "<<val<<endl;

        if(val < K){
            PutBack(col[val]);
            col[val] = newcol;
        }
    }
}

Compilation message (stderr)

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:183:13: warning: unused variable 'rep' [-Wunused-variable]
  183 |         int rep = ret[2];
      |             ^~~

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