Submission #630216

#	Time	Username	Problem	Language	Result	Execution time	Memory
630216		pooyashams	Library (JOI18_library)	C++14	100 / 100	480 ms	308 KiB

library

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

const int maxn = 1010;

int ans[maxn];
int n;

inline int bisect(int x)
{
	vector<int> c1(n, 0);
	vector<int> rem;
	for(int i = 0; i < x; i++)
		c1[ans[i]] = 1;
	for(int i = 0; i < n; i++)
		if(!c1[i])
			rem.push_back(i);
	int down = 0;
	int up = rem.size();
	while(up-down > 1)
	{
		int mid = (up+down) / 2;
		vector<int> m1 = c1;
		vector<int> m2(n, 0);
		for(int j = down; j < mid; j++)
		{
			m1[rem[j]] = 1;
			m2[rem[j]] = 1;
		}
		if(Query(m1) == Query(m2))
			up = mid;
		else
			down = mid;
	}
	return rem[down];
}

void Solve(int N)
{
	n = N;
	if(n == 1)
		return Answer({1});
	for(int i = 0; i < n; i++)
	{
		vector<int> m(n, 1);
		m[i] = 0;
		if(Query(m) == 1)
		{
			ans[0] = i;
			break;
		}
	}
	for(int i = 1; i < n; i++)
		ans[i] = bisect(i);
	vector<int> A(n);
	for(int i = 0; i < n; i++)
		A[i] = ans[i]+1;
	Answer(A);
}

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