Submission #440883

#	Time	Username	Problem	Language	Result	Execution time	Memory
440883		79brue	Shopping (JOI21_shopping)	C++14	100 / 100	146 ms	47308 KiB

Anna

#include <bits/stdc++.h>
#include "Anna.h"
#ifdef TEST
#define my_printf printf
#else
static void my_printf(const char* s, ...){

}
#endif // TEST

using namespace std;

typedef long long ll;

namespace Anna{
    int n, l, r, m;
    int firstVertex, firstL, firstR, depth;
    int turnsLeft = 18;
    int arr[1000002];

    int binaryL, binaryR, binaryM;
    int nowL, nowR;
    int start, len;
    int notIncludeL, notIncludeR;

    vector<bool> finalInfo;
    vector<int> link[1000002];
    int par[1000002];

    int minCover(int x){
        for(int i=1; i<=30; i++) if(x <= (1<<i)) return i;
        exit(1);
    }

    void InitA(int N, int L, int R){
        n = N, l = L, r = R;
        n = 1000000;
        firstVertex = 0, firstL = 0, firstR = n-1;
        while(depth < 13){
            int m = (firstL + firstR) / 2;
            if(r <= m){
                firstVertex *= 2;
                depth++;
                firstR = m;
            }
            else if(l > m){
                firstVertex = firstVertex * 2 + 1;
                depth++;
                firstL = m+1;
            }
            else break;
        }

        if(depth <= 1){
            SendA(0);
            SendA(0);
            SendA(depth);
            turnsLeft -= 3;
        }
        else{
            depth += 2;
            SendA(!!(depth & 8));
            SendA(!!(depth & 4));
            SendA(!!(depth & 2));
            SendA(!!(depth & 1));
            turnsLeft -= 4;
            depth -= 2;
        }
        for(int i=0; i<depth; i++) SendA(!!(firstVertex & (1<<i)));
        turnsLeft -= depth;

        binaryL = 1;
        binaryR = firstR-firstL;
        binaryM = (binaryL + binaryR) / 2;
        m = (firstL+firstR)/2;

        nowL = firstL, nowR = firstR;
        notIncludeL = m, notIncludeR = m+1;
        start = 0;
        len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);

        my_printf("Initialize Result (Anna): firstL %d, firstR %d, m %d\n", firstL, firstR, m);
    }

    void RecieveA(bool x){
        if(!turnsLeft){
            finalInfo.push_back(x);
            return;
        }

        len--;
        start = start*2+x;
        if(!len){
            int minAble = max(nowL, m+1-binaryM);
            int p = minAble + start;
            int q = p + binaryM;

            my_printf("Anna: %d %d %d %d\n", nowL, nowR, notIncludeL, notIncludeR);
            my_printf("Want to ask: [%d, %d] / Send: %d\n", p, q, start);
            if(p <= l && r <= q){
                SendA(1);

                nowL = p, nowR = q;
                binaryR = binaryM-1;
                binaryM = (binaryL + binaryR) / 2;
                start = 0;
                len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
            }
            else{
                SendA(0);

                notIncludeL = p, notIncludeR = q;
                binaryL = binaryM+1;
                binaryM = (binaryL + binaryR) / 2;
                start = 0;
                len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
            }
            turnsLeft--;
        }
    }

    void dfs(int x, int y){
        arr[x] = y;
        for(auto nxt: link[x]) dfs(nxt, y+1);
    }

    int Answer(){
        int rangeMin = 0;
        for(int i=0; i<20; i++) if(finalInfo[i]) rangeMin += (1<<i);

        reverse(finalInfo.begin(), finalInfo.end());
        for(int i=0; i<20; i++) finalInfo.pop_back();
        reverse(finalInfo.begin(), finalInfo.end());

        vector<int> indices;
        for(int i=nowL; i<notIncludeL; i++) indices.push_back(i);
        indices.push_back(rangeMin);
        for(int i=notIncludeR+1; i<=nowR; i++) indices.push_back(i);
        my_printf("Anna: indices size %d, finalInfo size %d\n", (int)indices.size(), (int)finalInfo.size());

        for(int i=nowL; i<=nowR; i++) arr[i] = 1e9;
        assert(finalInfo.size() == indices.size() * 2);

        int pnt = 0;
        vector<int> stk;
        memset(par, -1, sizeof(par));

        for(auto x: indices){
            while(1){
                int child = -1;
                if(pnt == (int)finalInfo.size()) break;
                if(finalInfo[pnt] == 1){
                    if(!stk.empty()) par[x] = stk.back();
                    stk.push_back(x);
                    pnt++;
                    break;
                }
                else{
                    if(child != -1) par[child] = stk.back();
                    par[stk.back()] = x, child = stk.back();
                    stk.pop_back();
                    pnt++;
                }
            }
        }

        int root = -1;
        for(auto x: indices){
            if(par[x] != -1) link[par[x]].push_back(x);
            else root = x;
        }
        dfs(root, 0);
        return min_element(arr+l, arr+r+1) - arr;
    }
}

void InitA(int N, int L, int R){
    Anna::InitA(N, L, R);
}

void ReceiveA(bool x){
    Anna::RecieveA(x);
}

int Answer() {
    return Anna::Answer();
}

Bruno

#include <bits/stdc++.h>
#include "Bruno.h"
#ifdef TEST
#define my_printf printf
#else
static void my_printf(const char* s, ...){

}
#endif // TEST

using namespace std;

typedef long long ll;

namespace Bruno{
    int n;
    int arr[1000002];
    int l, r;
    int depth, state, start, cnt;
    int turnsLeft = 18;

    int m, len;
    int rangeL[1000002], rangeR[1000002];
    int binaryL, binaryR, binaryM;
    int nowL, nowR;
    int notIncludeL, notIncludeR;

    void InitB(int N, vector<int> P) {
        n = N;
        for(int i=0; i<1000000; i++){
            if(i < n) arr[i] = P[i];
            else arr[i] = i;
        }
        n = 1000000;
    }

    void init_binary(){
        rangeL[1] = m, rangeR[1] = m+1;
        for(int i=2; i<=r-l; i++){
            if(rangeL[i-1] == l) rangeL[i] = l, rangeR[i] = rangeR[i-1]+1;
            else if(rangeR[i-1] == r) rangeR[i] = r, rangeL[i] = rangeL[i-1]-1;
            else if(arr[rangeL[i-1]-1] > arr[rangeR[i-1]+1]) rangeL[i] = rangeL[i-1]-1, rangeR[i] = rangeR[i-1];
            else rangeL[i] = rangeL[i-1], rangeR[i] = rangeR[i-1]+1;
        }
        binaryL = 1, binaryR = r-l;
    }

    int minCover(int x){
        for(int i=1; i<=30; i++) if(x <= (1<<i)) return i;
        exit(1);
    }

    void ReceiveB(bool y){
        bool alreadyUsed = 0;

        cnt++, turnsLeft--;
        if(state == 0){ /// 아직 깊이도 완성하지 못한 상태
            depth = depth * 2 + y;
            if(cnt == 3 && depth<=1) state = (depth==0 ? 2 : 1), cnt = 0;
            else if(cnt == 4) state = 1, depth-=2, cnt = 0;
            if(state!=2) return;
            else goto term;
        }
        if(state == 1){ /// 시작 정점을 입력받는 중인 상태
            start = start * 2 + y;
            if(depth == cnt){
                term:
                state = 2, cnt = 0;
                l = 0, r = n-1;
                for(int i=0; i<depth; i++){
                    int M = (l+r) / 2;
                    if(start & (1<<i)) l = M+1;
                    else r = M;
                }
                m = (l+r)/2;
                init_binary();

                binaryL = 1;
                binaryR = r-l;
                binaryM = (binaryL + binaryR) / 2;

                nowL = l, nowR = r;
                notIncludeL = m, notIncludeR = m+1;
                start = 0;
                len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
                alreadyUsed = 1;
                state = 2;

                my_printf("Initialize Result (Bruno): firstL %d, firstR %d, m %d\n", l, r, m);
            }
            else return;
        }
        if(!alreadyUsed){
            if(y){ /// Bruno가 물어본 구간에 Anna의 구간이 포함된다.
                nowL = rangeL[binaryM], nowR = rangeR[binaryM];
                binaryR = binaryM-1;
                binaryM = (binaryL + binaryR) / 2;
                start = 0;
                len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
            }
            else{
                notIncludeL = rangeL[binaryM], notIncludeR = rangeR[binaryM];
                binaryL = binaryM+1;
                binaryM = (binaryL + binaryR) / 2;
                start = 0;
                len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
            }
        }
        if(turnsLeft){ /// 이분 탐색을 진행해야 하는 상태
            int minAble = max(nowL, m+1-binaryM);
            int val = rangeL[binaryM] - minAble;
            assert(val < (1<<len));

            my_printf("Bruno: %d %d %d %d\n", nowL, nowR, notIncludeL, notIncludeR);
            my_printf("Want to ask: [%d, %d] / Send: %d\n", rangeL[binaryM], rangeR[binaryM], val);
            for(int i=len-1; i>=0; i--) SendB(!!(val & (1<<i)));
            return;
        }

        /// 카르테시안 트리 보내기
        int rangeMin = notIncludeL;
        for(int i=notIncludeL+1; i<=notIncludeR; i++){
            if(arr[rangeMin] > arr[i]) rangeMin = i;
        }

        for(int i=0; i<20; i++) SendB(!!(rangeMin & (1<<i)));

        vector<pair<int, int> > vec;
        stack<int> stk;
        for(int i=nowL; i<notIncludeL; i++) vec.push_back(make_pair(i, arr[i]));
        vec.push_back(make_pair(rangeMin, arr[rangeMin]));
        for(int i=notIncludeR+1; i<=nowR; i++) vec.push_back(make_pair(i, arr[i]));
        my_printf("Bruno: vec size %d\n", (int)vec.size());

        for(auto x: vec){
            while(!stk.empty() && stk.top() > x.second){
                stk.pop();
                SendB(0);
            }
            stk.push(x.second);
            SendB(1);
        }
        while(!stk.empty()){
            stk.pop();
            SendB(0);
        }
    }
}

void InitB(int N, vector<int> P){
    Bruno::InitB(N, P);
}

void ReceiveB(bool x){
    Bruno::ReceiveB(x);
}

• Subtask 1: 1 / 1
• Subtask 2: 9 / 9
• Subtask 3: 90 / 90