Submission #48073

#	Time	Username	Problem	Language	Result	Execution time	Memory
48073		kawaiigrabrielneko	Library (JOI18_library)	C++14	100 / 100	489 ms	668 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

void Solve(int N){
	vector<int> A(N);
	vector<int> B(N);
	vector<int> AP(N);
	vector<int> AMB(N);
	vector<int> APUB(N);
	int na = N/2;
	vector<int> ans(N);
	if (N==1){
        A[0] = 1;
        Answer(A);
        return;
	}
	for (int i = 0; i < N/2; i++){
        A[i] = 1;
        AP[i] = 0;
	}
	for (int i = N/2; i < N; i++){
        A[i] = 0;
        AP[i] = 1;
	}
	if (Query(A)<Query(AP)){
        for (int i = 0; i < N; i++){
            A[i] = 1 - A[i];
            AP[i] = 1 - AP[i];
        }
        na = N - na;
	}
	// A contains an endpoint
	while (na > 1){
        int nb = na/2;
        int ct = 0;
        for (int i = 0; i < N; i++){
            if (A[i]==1&&ct<nb){
                B[i] = 1;
                ct++;
            }
            else B[i] = 0;
            AMB[i] = A[i] - B[i];
            APUB[i] = 1 - AMB[i];
        }
        if (Query(AMB)<Query(APUB)){ // Endpoint in B
            for (int i = 0; i < N; i++){
                A[i] = B[i];
            }
            na = nb;
        }
        else { // Endpoint in A - B
            for (int i = 0; i < N; i++){
                A[i] = AMB[i];
            }
            na = na - nb;
        }
	}
	for (int i = 0; i < N; i++){
        if (A[i] == 1) ans[0] = i;
	}
	vector<int> M(N);
	vector<int> K(N);
	for (int i = 1; i < N; i++){
        int nm = N-i;
        for (int j = 0; j < N; j++){
            M[j] = 1;
        }
        for (int j = 0; j < i; j++){
            M[ans[j]] = 0;
        }
        while (nm > 1){
            int nk = nm/2;
            int ct = 0;
            for (int j = 0; j < N; j++){
                if (M[j]==1&&ct<nk){
                    ct++;
                    K[j] = 1;
                }
                else K[j] = 0;
            }
            int x = Query(K);
            K[ans[i-1]] = 1;
            if (x==Query(K)){
                K[ans[i-1]] = 0;
                nm = nk;
                for (int j = 0; j < N; j++){
                    M[j] = K[j];
                }
            }
            else {
                K[ans[i-1]] = 0;
                nm = nm - nk;
                for (int j = 0; j < N; j++){
                    M[j] = M[j] - K[j];
                }
            }
        }
        for (int j = 0; j < N; j++){
            if (M[j]==1) ans[i] = j;
        }
	}
	for (int i = 0; i < N; i++){
        ans[i]++;
	}
	Answer(ans);
}

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