oj.uz

답안 #481887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481887 2021-10-22T05:37:31 Z Haruto810198 최후의 만찬 (IOI12_supper) C++17
0 / 100
 438 ms 29200 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

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);
        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){
        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:154:13: warning: unused variable 'rep' [-Wunused-variable]
  154 |         int rep = ret[2];
      |             ^~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5248 KB Output is correct
2 Incorrect 2 ms 5232 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 7460 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 351 ms 25016 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5644 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 437 ms 28316 KB Output isn't correct - not an optimal way
2 Incorrect 423 ms 28372 KB Output isn't correct - not an optimal way
3 Incorrect 420 ms 28332 KB Output isn't correct - not an optimal way
4 Incorrect 413 ms 28500 KB Output isn't correct - not an optimal way
5 Incorrect 438 ms 28512 KB Output isn't correct - not an optimal way
6 Incorrect 420 ms 28528 KB Output isn't correct - not an optimal way
7 Incorrect 416 ms 28380 KB Output isn't correct - not an optimal way
8 Incorrect 428 ms 28420 KB Output isn't correct - not an optimal way
9 Incorrect 415 ms 28388 KB Output isn't correct - not an optimal way
10 Correct 423 ms 29200 KB Output is partially correct - 1500000 bits used