oj.uz

Submission #334123

# Submission time Handle Problem Language Result Execution time Memory
334123 2020-12-08T11:19:08 Z CaroLinda Library (JOI18_library) C++14
100 / 100
 390 ms 640 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 492 KB # of queries: 2550
2 Correct 44 ms 364 KB # of queries: 2531
3 Correct 40 ms 620 KB # of queries: 2706
4 Correct 58 ms 364 KB # of queries: 2704
5 Correct 49 ms 364 KB # of queries: 2702
6 Correct 36 ms 364 KB # of queries: 2698
7 Correct 45 ms 620 KB # of queries: 2682
8 Correct 48 ms 396 KB # of queries: 2585
9 Correct 28 ms 380 KB # of queries: 2693
10 Correct 22 ms 364 KB # of queries: 1569
11 Correct 1 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 5
14 Correct 1 ms 364 KB # of queries: 10
15 Correct 2 ms 364 KB # of queries: 91
16 Correct 4 ms 364 KB # of queries: 201

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 492 KB # of queries: 2550
2 Correct 44 ms 364 KB # of queries: 2531
3 Correct 40 ms 620 KB # of queries: 2706
4 Correct 58 ms 364 KB # of queries: 2704
5 Correct 49 ms 364 KB # of queries: 2702
6 Correct 36 ms 364 KB # of queries: 2698
7 Correct 45 ms 620 KB # of queries: 2682
8 Correct 48 ms 396 KB # of queries: 2585
9 Correct 28 ms 380 KB # of queries: 2693
10 Correct 22 ms 364 KB # of queries: 1569
11 Correct 1 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 5
14 Correct 1 ms 364 KB # of queries: 10
15 Correct 2 ms 364 KB # of queries: 91
16 Correct 4 ms 364 KB # of queries: 201
17 Correct 390 ms 492 KB # of queries: 18122
18 Correct 328 ms 492 KB # of queries: 17975
19 Correct 333 ms 492 KB # of queries: 18162
20 Correct 339 ms 620 KB # of queries: 16966
21 Correct 208 ms 548 KB # of queries: 15915
22 Correct 344 ms 532 KB # of queries: 18190
23 Correct 354 ms 364 KB # of queries: 18143
24 Correct 149 ms 364 KB # of queries: 8359
25 Correct 342 ms 580 KB # of queries: 17739
26 Correct 300 ms 492 KB # of queries: 16511
27 Correct 147 ms 492 KB # of queries: 8295
28 Correct 353 ms 640 KB # of queries: 16956
29 Correct 308 ms 620 KB # of queries: 16937
30 Correct 313 ms 492 KB # of queries: 16956