Submission #639423

#	Time	Username	Problem	Language	Result	Execution time	Memory
639423		beaconmc	Library (JOI18_library)	C++14	100 / 100	472 ms	508 KiB

library

#include <bits/stdc++.h>
typedef int ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


#include "library.h"
using namespace std;

ll b = 0;
ll n = 1;
unordered_set<ll> sussies;

int q(vector<int> arr){
	if (arr.size()==0) return 0;
	vector<ll> query(n);
	for (auto&i : arr){
		query[i] = 1;
	}
	return Query(query);
}

bool begins(vector<int> oldarr){
	vector<int> arr;
	for (auto&i : oldarr){
		if (!sussies.count(i)) arr.push_back(i);
	}

	int result = q(arr);
	arr.push_back(b);
	int result2 = q(arr);
	if (result == result2) return 1;
	return 0;
}


void Solve(int N)
{
	n = N;

	FOR(i,0,n){
		vector<ll> queries;
		FOR(j,0,n){
			if (j!=i) queries.push_back(j);
		}
		if (q(queries)==1){
			b = i;
			break;
		}
	}
	vector<ll> ans;
	ans.push_back(b);
	sussies.insert(b);


	FOR(i,0,n-1){
		vector<int> stuff;

		FOR(j,0,n){
			if (!sussies.count(j)) stuff.push_back(j);
		}
		ll l=0;
		ll r = stuff.size();

		while (l<r){
			vector<ll> queries;
			ll mid = (l+r)/2;
			FOR(i,l,mid+1){
				queries.push_back(stuff[i]);
			}

			bool sus = begins(queries);


			if (sus) r = mid;
			else l = mid+1;
		}
		b = stuff[l];
		sussies.insert(b);
		ans.push_back(b);

	};

	FOR(i,0,n){
		ans[i] += 1;
	}

	Answer(ans);

}

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