oj.uz

Submission #481889

# Submission time Handle Problem Language Result Execution time Memory
481889 2021-10-22T06:28:23 Z Haruto810198 Last supper (IOI12_supper) C++17
34 / 100
 478 ms 35196 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; // 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;

}

#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7552 KB Output is correct
2 Correct 4 ms 7548 KB Output is correct
3 Correct 6 ms 7824 KB Output is correct
4 Correct 10 ms 8276 KB Output is correct
5 Correct 12 ms 8508 KB Output is correct
6 Correct 18 ms 8824 KB Output is correct
7 Correct 16 ms 8836 KB Output is correct
8 Correct 20 ms 8832 KB Output is correct
9 Correct 20 ms 8868 KB Output is correct
10 Correct 22 ms 8988 KB Output is correct
11 Correct 21 ms 8816 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10112 KB Output is correct
2 Correct 195 ms 19248 KB Output is correct
3 Correct 466 ms 35196 KB Output is correct
4 Correct 338 ms 28212 KB Output is correct
5 Correct 412 ms 30768 KB Output is correct
6 Correct 456 ms 32520 KB Output is correct
7 Correct 460 ms 33760 KB Output is correct
8 Correct 394 ms 31348 KB Output is correct
9 Correct 276 ms 25508 KB Output is correct
10 Correct 464 ms 34312 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 28772 KB Output is correct
2 Correct 462 ms 33892 KB Output is correct
3 Correct 462 ms 33900 KB Output is correct
4 Correct 457 ms 33756 KB Output is correct
5 Correct 439 ms 33092 KB Output is correct
6 Correct 471 ms 33892 KB Output is correct
7 Correct 451 ms 33776 KB Output is correct
8 Correct 446 ms 34664 KB Output is correct
9 Correct 423 ms 33464 KB Output is correct
10 Correct 466 ms 33808 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8188 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 32684 KB Output is partially correct - 1500000 bits used
2 Correct 467 ms 32920 KB Output is partially correct - 1500000 bits used
3 Correct 478 ms 32784 KB Output is partially correct - 1500000 bits used
4 Correct 451 ms 32820 KB Output is partially correct - 1500000 bits used
5 Correct 473 ms 32724 KB Output is partially correct - 1500000 bits used
6 Correct 461 ms 32748 KB Output is partially correct - 1500000 bits used
7 Correct 455 ms 32692 KB Output is partially correct - 1497585 bits used
8 Correct 457 ms 32816 KB Output is partially correct - 1500000 bits used
9 Correct 460 ms 32688 KB Output is partially correct - 1500000 bits used
10 Correct 471 ms 33532 KB Output is partially correct - 1500000 bits used