Submission #334123

#	Time	Username	Problem	Language	Result	Execution time	Memory
334123		CaroLinda	Library (JOI18_library)	C++14	100 / 100	390 ms	640 KiB

library

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

#define debug 
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)(x.size())

using namespace std;

int N ;
vector<int> M ;
vector< vector<int> > adj ;

bool thereIsAdjacency(int x )
{
	M[x] = 1 ;
	int a = Query(M) ;
	M[x] = 0 ;
	int b = Query(M) ;

	return b >= a ;
}

void findAdjacency(vector<int> vec , int x)
{
	
	if(sz(vec) == 1)
	{
		adj[ vec[0] ].push_back(x) ;
		adj[x].push_back( vec[0] ) ;

		return ;
	}

	vector<int> newVec ;

	for(int i = 0 ; i < sz(vec)>>1 ; i++ ) M[ vec[i] ] = 1 ;

	bool thereIs = thereIsAdjacency(x) ;

	for(int i = 0 ; i < sz(vec)>>1 ; i++ ) M[ vec[i] ] = 0 ;

	if( thereIs ) 
	{
		for(int i = 0 ; i < sz(vec)>>1 ; i++ ) newVec.push_back(vec[i]) ;
		return (void)(findAdjacency(newVec,x)) ;
	}

	for(int i = sz(vec)>>1 ; i < sz(vec) ; i++ )
		newVec.push_back(vec[i]) ;

	findAdjacency(newVec, x) ;

}

void Solve(int n)
{
	if(n == 1) return (void)( Answer({1}) ) ;

	N = n ;

	adj.resize(N, vector<int>() ) ;
	M.resize(N,0) ;

	vector<int> tails ;

	for(int i = 0 ; i < N ; i++ ) M[i] = 1 ;
	for(int i = 0 ; i < N ; i++ )
	{
		M[i] = 0 ;
		if( Query(M) == 1 ) tails.push_back(i) ;
		M[i] = 1 ;
	}
	for(int i = 0 ; i < N ; i++ ) M[i] = 0 ;

	int cur = tails[0] ;
	vector<bool> vis(N,false) ;
	vector<int> ans ;

	while( cur != tails[1] )
	{
		int i = cur ;

		ans.push_back(i+1) ;

		vis[i] = true ;
		vector<int> vec ;

		for(int j = 0 ; j <N ; j++ )
			if(!vis[j]) vec.push_back(j) ;

		findAdjacency(vec,i ) ;

		cur = adj[i].back() ;

	}

	ans.push_back(tails[1] + 1) ;

	Answer(ans) ;

}

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