Submission #827838

#	Time	Username	Problem	Language	Result	Execution time	Memory
827838		MohamedAhmed04	Library (JOI18_library)	C++14	100 / 100	217 ms	592 KiB

library

#include <bits/stdc++.h>
#include "library.h"

using namespace std;

const int MAX = 1000 + 10 ;

int n ;

vector<int>v[MAX] ;
int taken[MAX] ;

bool check(int l , int r)
{
	vector<int>vq(n , 0) ;
	int cnt = r-l+1 ;
	for(int i = l ; i <= r ; ++i)
	{
		vq[i] = 1 ;
		for(auto &j : v[i])
			cnt -= (j > i && j <= r) ;
	}
	return (Query(vq) < cnt) ;
}

void Find_Adjacent(int idx , int cnt)
{
	for(int i = 0 ; i < cnt ; ++i)
	{
		int l = 0 , r = idx ;
		int idx2 = -1 ; 
		while(l <= r)
		{
			int mid = (l + r) >> 1 ;
			if(check(mid , idx))
				idx2 = mid , l = mid+1 ;
			else
				r = mid-1 ;
		}
		v[idx].push_back(idx2) , v[idx2].push_back(idx) ;
	}
}

void Solve(int N)
{
	n = N ;
	if(n == 1)
	{
		Answer({1}) ;
		return ;
	}
	vector<int>vq(n , 0) ;
	int cur = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		++cur ;
		vq[i] = 1 ;
		int x = Query(vq) ;
		Find_Adjacent(i , cur - x) ;
		cur = x ;
	}
	vector<int>ans ;
	int x = -1 ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(v[i].size() == 1)
		{
			x = i ;
			break ;
		}
	}
	while(ans.size() < n)
	{
		ans.push_back(x+1) ;
		taken[x] = 1 ;
		for(auto &i : v[x])
		{
			if(!taken[i])
			{
				x = i ;
				break ;
			}
		}
	}
	Answer(ans) ;
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:72:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  while(ans.size() < n)
      |        ~~~~~~~~~~~^~~

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