oj.uz

Submission #440883

# Submission time Handle Problem Language Result Execution time Memory
440883 2021-07-03T12:26:18 Z 79brue Shopping (JOI21_shopping) C++14
100 / 100
 146 ms 47308 KB 
#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();
}

#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31732 KB Output is correct
2 Correct 19 ms 31768 KB Output is correct
3 Correct 18 ms 31848 KB Output is correct
4 Correct 16 ms 31796 KB Output is correct
5 Correct 18 ms 31800 KB Output is correct
6 Correct 17 ms 31844 KB Output is correct
7 Correct 20 ms 31784 KB Output is correct
8 Correct 17 ms 31800 KB Output is correct
9 Correct 17 ms 31812 KB Output is correct
10 Correct 19 ms 31852 KB Output is correct
11 Correct 16 ms 31852 KB Output is correct
12 Correct 19 ms 31864 KB Output is correct
13 Correct 18 ms 31752 KB Output is correct
14 Correct 17 ms 31860 KB Output is correct
15 Correct 19 ms 31796 KB Output is correct
16 Correct 19 ms 31800 KB Output is correct
17 Correct 16 ms 31800 KB Output is correct
18 Correct 17 ms 31812 KB Output is correct
19 Correct 20 ms 31808 KB Output is correct
20 Correct 17 ms 31752 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31732 KB Output is correct
2 Correct 19 ms 31768 KB Output is correct
3 Correct 18 ms 31848 KB Output is correct
4 Correct 16 ms 31796 KB Output is correct
5 Correct 18 ms 31800 KB Output is correct
6 Correct 17 ms 31844 KB Output is correct
7 Correct 20 ms 31784 KB Output is correct
8 Correct 17 ms 31800 KB Output is correct
9 Correct 17 ms 31812 KB Output is correct
10 Correct 19 ms 31852 KB Output is correct
11 Correct 16 ms 31852 KB Output is correct
12 Correct 19 ms 31864 KB Output is correct
13 Correct 18 ms 31752 KB Output is correct
14 Correct 17 ms 31860 KB Output is correct
15 Correct 19 ms 31796 KB Output is correct
16 Correct 19 ms 31800 KB Output is correct
17 Correct 16 ms 31800 KB Output is correct
18 Correct 17 ms 31812 KB Output is correct
19 Correct 20 ms 31808 KB Output is correct
20 Correct 17 ms 31752 KB Output is correct
21 Correct 21 ms 32136 KB Output is correct
22 Correct 18 ms 31920 KB Output is correct
23 Correct 18 ms 32048 KB Output is correct
24 Correct 22 ms 32008 KB Output is correct
25 Correct 17 ms 31952 KB Output is correct
26 Correct 19 ms 32052 KB Output is correct
27 Correct 19 ms 32080 KB Output is correct
28 Correct 19 ms 31920 KB Output is correct
29 Correct 19 ms 31924 KB Output is correct
30 Correct 18 ms 31888 KB Output is correct
31 Correct 20 ms 32056 KB Output is correct
32 Correct 19 ms 31940 KB Output is correct
33 Correct 19 ms 31868 KB Output is correct
34 Correct 18 ms 31916 KB Output is correct
35 Correct 20 ms 31916 KB Output is correct
36 Correct 18 ms 31916 KB Output is correct
37 Correct 18 ms 31856 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 45932 KB Output is correct
2 Correct 115 ms 43924 KB Output is correct
3 Correct 120 ms 43484 KB Output is correct
4 Correct 131 ms 47308 KB Output is correct
5 Correct 121 ms 46572 KB Output is correct
6 Correct 116 ms 45788 KB Output is correct
7 Correct 134 ms 43892 KB Output is correct
8 Correct 115 ms 43592 KB Output is correct
9 Correct 110 ms 43500 KB Output is correct
10 Correct 122 ms 43460 KB Output is correct
11 Correct 130 ms 46536 KB Output is correct
12 Correct 115 ms 43460 KB Output is correct
13 Correct 123 ms 43504 KB Output is correct
14 Correct 117 ms 44440 KB Output is correct
15 Correct 118 ms 44136 KB Output is correct
16 Correct 119 ms 44916 KB Output is correct
17 Correct 129 ms 44144 KB Output is correct
18 Correct 115 ms 43756 KB Output is correct
19 Correct 146 ms 43624 KB Output is correct
20 Correct 116 ms 43496 KB Output is correct
21 Correct 127 ms 43504 KB Output is correct
22 Correct 124 ms 43520 KB Output is correct
23 Correct 118 ms 43496 KB Output is correct
24 Correct 120 ms 43604 KB Output is correct
25 Correct 133 ms 43464 KB Output is correct
26 Correct 121 ms 43504 KB Output is correct
27 Correct 145 ms 43612 KB Output is correct
28 Correct 114 ms 43552 KB Output is correct
29 Correct 116 ms 43460 KB Output is correct
30 Correct 115 ms 43512 KB Output is correct