oj.uz

Submission #482694

# Submission time Handle Problem Language Result Execution time Memory
482694 2021-10-26T04:12:08 Z Haruto810198 Last supper (IOI12_supper) C++17
100 / 100
 359 ms 32592 KB 
#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;

}

#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);
        }

    }

}

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7652 KB Output is correct
2 Correct 3 ms 7652 KB Output is correct
3 Correct 6 ms 7944 KB Output is correct
4 Correct 11 ms 8228 KB Output is correct
5 Correct 17 ms 8888 KB Output is correct
6 Correct 15 ms 8972 KB Output is correct
7 Correct 13 ms 8964 KB Output is correct
8 Correct 17 ms 8896 KB Output is correct
9 Correct 17 ms 8864 KB Output is correct
10 Correct 15 ms 8900 KB Output is correct
11 Correct 15 ms 8844 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10220 KB Output is correct
2 Correct 136 ms 19232 KB Output is correct
3 Correct 338 ms 32260 KB Output is correct
4 Correct 334 ms 31216 KB Output is correct
5 Correct 341 ms 31416 KB Output is correct
6 Correct 356 ms 31344 KB Output is correct
7 Correct 339 ms 31500 KB Output is correct
8 Correct 268 ms 29560 KB Output is correct
9 Correct 322 ms 29740 KB Output is correct
10 Correct 347 ms 31764 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 28208 KB Output is correct
2 Correct 345 ms 31704 KB Output is correct
3 Correct 359 ms 31700 KB Output is correct
4 Correct 338 ms 31504 KB Output is correct
5 Correct 317 ms 30740 KB Output is correct
6 Correct 351 ms 31836 KB Output is correct
7 Correct 355 ms 31528 KB Output is correct
8 Correct 354 ms 32516 KB Output is correct
9 Correct 299 ms 31036 KB Output is correct
10 Correct 336 ms 31620 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8616 KB Output is correct
2 Correct 15 ms 8884 KB Output is correct
3 Correct 15 ms 8880 KB Output is correct
4 Correct 15 ms 8892 KB Output is correct
5 Correct 15 ms 8868 KB Output is correct
6 Correct 15 ms 8896 KB Output is correct
7 Correct 16 ms 8884 KB Output is correct
8 Correct 17 ms 8968 KB Output is correct
9 Correct 15 ms 8892 KB Output is correct
10 Correct 13 ms 8908 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 31580 KB Output is correct - 120000 bits used
2 Correct 333 ms 31796 KB Output is correct - 122000 bits used
3 Correct 323 ms 31636 KB Output is correct - 125000 bits used
4 Correct 334 ms 31776 KB Output is correct - 125000 bits used
5 Correct 319 ms 31556 KB Output is correct - 125000 bits used
6 Correct 334 ms 31692 KB Output is correct - 125000 bits used
7 Correct 322 ms 31624 KB Output is correct - 124828 bits used
8 Correct 334 ms 31904 KB Output is correct - 124910 bits used
9 Correct 332 ms 31632 KB Output is correct - 125000 bits used
10 Correct 334 ms 32592 KB Output is correct - 125000 bits used