Submission #48560

#	Time	Username	Problem	Language	Result	Execution time	Memory
48560		ngkan146	Library (JOI18_library)	C++14	100 / 100	513 ms	4968 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

int cnt[1005][10];  // if bit x off -> insert i, else erase i

vector <int> askBitAll[10];
int cntAll[10], cntNum[10];
vector <int> G[1005];
vector <int> ans;

int cntMask[1024];
int cntnumMask[1024];
vector <int> askMask[1024];

void dfs(int u,int p){
    ans.push_back(u);
    for(auto v: G[u]){
        if (v == p) continue;
        dfs(v, u);
    }
}

void Solve(int n){
    if (n == 1){
        ans.push_back(1);
        Answer(ans);
        return;
    }

    // build askMask
    for(int mask=0;mask<1024;mask++){
        askMask[mask].assign(n, 0);
        for(int i=1;i<=n;i++)
            cntnumMask[mask] += (i & mask) == mask,
            askMask[mask][i-1] = ((i & mask) == mask);
        if (cntnumMask[mask])
            cntMask[mask] = Query(askMask[mask]);
    }

    // build cnt all
    for(int bit=0;bit<10;bit++){
        askBitAll[bit].assign(n, 0);
        for(int j=1;j<=n;j++)
            cntNum[bit] += ((j>>bit)&1),
            askBitAll[bit][j-1] = ((j>>bit)&1);
        if (cntNum[bit])
            cntAll[bit] = Query(askBitAll[bit]);
    }
    // ask n * log times, prep cnt

	for(int i=1;i<=n;i++){
        for(int bit=0;bit<10;bit++){
            if (((i>>bit)&1) == 1)  cntNum[bit] --;
            else cntNum[bit] ++;
            askBitAll[bit][i-1] ^= 1;

            if (cntNum[bit])    cnt[i][bit] = Query(askBitAll[bit]);

            askBitAll[bit][i-1] ^= 1;
            if (((i>>bit)&1) == 1)  cntNum[bit] ++;
            else cntNum[bit] --;
        }
	}

	// find adj of i in log times
	for(int i=1;i<=n;i++){
        int mask = 0;
        int okBit = 0;
        for(int bit=0;bit<10;bit++){
            if (((i>>bit)&1) == 0){
                // don't have bit, try to insert
                if (cntAll[bit] - cnt[i][bit] == -1){
                    okBit |= (1<<bit);
                }
                else if (cntAll[bit] == cnt[i][bit]){
                    // hmm
                }
                else{
                    okBit |= (1<<bit);
                    mask += (1<<bit);
                }
            }
            else{
                // have bit, try to remove
                if (cntAll[bit] - cnt[i][bit] == 1){
                    okBit |= (1<<bit);
                }
                else if (cntAll[bit] == cnt[i][bit]){
                    // hmm
                }
                else{
                    okBit |= (1<<bit);
                    mask += (1<<bit);
                }
            }
        }
        //cout << i << ' '<< mask << ' ' << okBit << endl;
        int firstAdj = mask, secondAdj = mask;
        for(int bit=0;bit<10;bit++){
            //cout << i << ' ' << bit << endl;
            if (((okBit>>bit)&1) == 1) continue;
            if (firstAdj + (1<<bit) > n){
                secondAdj += (1<<bit);
                continue;
            }
            if (secondAdj + (1<<bit) > n){
                firstAdj += (1<<bit);
                continue;
            }
            //cout << "process " << ' ' << bit << endl;
            int finalMask = firstAdj + (1<<bit);

            if ((i & finalMask) == finalMask){
                askMask[finalMask][i-1] = 0;
                int ask = (cntnumMask[finalMask] == 1 ? 0 : Query(askMask[finalMask]));
                if (cntMask[finalMask] - ask == 1)
                    secondAdj += (1<<bit);
                else
                    firstAdj += (1<<bit);
                askMask[finalMask][i-1] = 1;
            }
            else{
                askMask[finalMask][i-1] = 1;
                int ask = Query(askMask[finalMask]);
                if (cntMask[finalMask] - ask == -1)
                    secondAdj += (1<<bit);
                else
                    firstAdj += (1<<bit);
                askMask[finalMask][i-1] = 0;
            }
        }
        //cout << i << ' ' << firstAdj << ' ' << secondAdj << endl;
        if (firstAdj)
            G[i].push_back(firstAdj);
        if (secondAdj)
            G[i].push_back(secondAdj);
	}

	for(int i=1;i<=n;i++){
        if (G[i].size() == 1){
            dfs(i, i);
            break;
        }
	}
	Answer(ans);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81