Submission #61718

#	Time	Username	Problem	Language	Result	Execution time	Memory
61718		mAng0	Library (JOI18_library)	C++17	100 / 100	734 ms	704 KiB

library

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

vector<int> global_M;
vector<int> ban;
vector<int> ans;
int n, last;

int task_one(int s, int e){
    if(s == e) return s;
    int mid = (s + e) / 2;
    for(int i=0;i<n;i++) global_M[i] = 0;
    for(int i=s;i<=mid;i++){
        global_M[i] = 1;
    }
    int one = Query(global_M);
    for(int i=0;i<n;i++) global_M[i] = 1 - global_M[i];
    int two = Query(global_M);
    if(one >= two) return task_one(s, mid);
    else return task_one(mid+1, e);
}

int task_two(int s, int e){
    if(s == e) return s;
    int mid = (s + e) / 2;
    for(int i=0;i<n;i++) global_M[i] = 0;
    int cnt = 0;
    for(int i=s;i<=mid;i++){
        if(ban[i]) continue;
        global_M[i] = 1;
        cnt++;
    }
    if(cnt == 0) return task_two(mid+1, e);
    int one = Query(global_M);
    global_M[last] = 1;
    int two = Query(global_M);
    if(one == two) return task_two(s, mid);
    else return task_two(mid+1, e);
}

void Solve(int N)
{
    n = N;
    global_M.resize(N);
    ban.resize(N);
	last = task_one(0, n-1);
	//printf("hi, %d\n", last);
	ban[last] = 1;
    ans.push_back(last+1);
	for(int i=0;i<n-1;i++){
        last = task_two(0, n-1);
        //printf("hii, %d\n", last);
        ban[last] = 1;
	    ans.push_back(last+1);
	}
	Answer(ans);
}

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