oj.uz

Submission #140071

# Submission time Handle Problem Language Result Execution time Memory
140071 2019-08-02T01:52:15 Z mahmoudbadawy Library (JOI18_library) C++17
100 / 100
 545 ms 552 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

// Query()
// Answer()
int n;

int query(vector<int> v)
{
	vector<int> m(n,0);
	for(int i:v) m[i]=1;
	return Query(m);
}

int get(int x,vector<int> v)
{
	if(v.size()==1)
	{
		/*v.push_back(x);
		if(query(v)==2)
			return -1;*/
		return v[0];
	}
	vector<int> mm;
	for(int i=0;i<v.size()/2;i++)
		mm.push_back(v[i]);
	int cur=query(mm);
	mm.push_back(x);
	if(query(mm)<=cur)
	{
		mm.pop_back();
		return get(x,mm);
	}
	mm.clear();
	for(int i=v.size()/2;i<v.size();i++)
		mm.push_back(v[i]);
	return get(x,mm);
}

vector<int> adj[1005];
vector<int> ans;
int vis[1005];

void build(int x,int pa)
{
	vis[x]=1;
	ans.push_back(x+1);
	for(int i:adj[x])
		if(!vis[i]) build(i,x);
}

vector<int> hv1;

int got(int x)
{
	if(adj[x].size()==2) return 1;
	if(hv1[0]==x||hv1[1]==x)
		if(adj[x].size()==1) return 1;
	return 0;
}

void Solve(int N)
{
	if(N==1)
		{Answer({1});return;}
	n=N;
	for(int i=0;i<N;i++)
	{
		vector<int> m(N,1);
		m[i]=0;
		if(Query(m)==1)
			hv1.push_back(i);
	}
	// calls = edges/2 -> 2000/2 -> 1000
	int calls=0;
	for(int i=0;i<N;i++)
	{
		while(true){
			if(got(i)) break;
			vector<int> ss;
			for(int j=0;j<N;j++)
			{
				bool ok=1;
				for(int k:adj[i])
					ok&=(k!=j);
				ok&=(i!=j);
				ok&=(!got(j));
				if(ok) ss.push_back(j);
			}
			int x=get(i,ss);
			if(x!=-1) {calls++; adj[i].push_back(x); adj[x].push_back(i);}
			else assert(i!=i);
		}
		//cout << i+1 << " Found " << x+1 << endl;
	}
	//cout << calls << endl;
	/*for(int i=0;i<n;i++)
	{
		cout << i+1 << ": ";
		for(int j:adj[i]) cout << j+1 << " ";
		cout << endl;
	}*/
	for(int i=0;i<n;i++)
	{
		if(adj[i].size()==1)
		{
			build(i,-1); break;
		}
	}
	Answer(ans);
}

Compilation message

library.cpp: In function 'int get(int, std::vector<int>)':
library.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size()/2;i++)
              ~^~~~~~~~~~~
library.cpp:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=v.size()/2;i<v.size();i++)
                       ~^~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 348 KB # of queries: 2700
2 Correct 50 ms 376 KB # of queries: 2715
3 Correct 42 ms 472 KB # of queries: 2866
4 Correct 52 ms 340 KB # of queries: 2868
5 Correct 48 ms 432 KB # of queries: 2864
6 Correct 37 ms 356 KB # of queries: 2838
7 Correct 41 ms 340 KB # of queries: 2858
8 Correct 50 ms 376 KB # of queries: 2739
9 Correct 56 ms 348 KB # of queries: 2849
10 Correct 22 ms 344 KB # of queries: 1651
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 2
13 Correct 2 ms 376 KB # of queries: 5
14 Correct 2 ms 376 KB # of queries: 10
15 Correct 4 ms 248 KB # of queries: 93
16 Correct 7 ms 376 KB # of queries: 229

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 348 KB # of queries: 2700
2 Correct 50 ms 376 KB # of queries: 2715
3 Correct 42 ms 472 KB # of queries: 2866
4 Correct 52 ms 340 KB # of queries: 2868
5 Correct 48 ms 432 KB # of queries: 2864
6 Correct 37 ms 356 KB # of queries: 2838
7 Correct 41 ms 340 KB # of queries: 2858
8 Correct 50 ms 376 KB # of queries: 2739
9 Correct 56 ms 348 KB # of queries: 2849
10 Correct 22 ms 344 KB # of queries: 1651
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 2
13 Correct 2 ms 376 KB # of queries: 5
14 Correct 2 ms 376 KB # of queries: 10
15 Correct 4 ms 248 KB # of queries: 93
16 Correct 7 ms 376 KB # of queries: 229
17 Correct 538 ms 508 KB # of queries: 18920
18 Correct 535 ms 380 KB # of queries: 18657
19 Correct 545 ms 528 KB # of queries: 18910
20 Correct 485 ms 424 KB # of queries: 17670
21 Correct 429 ms 424 KB # of queries: 16647
22 Correct 510 ms 500 KB # of queries: 18956
23 Correct 485 ms 384 KB # of queries: 18917
24 Correct 209 ms 360 KB # of queries: 8721
25 Correct 499 ms 504 KB # of queries: 18473
26 Correct 510 ms 504 KB # of queries: 17279
27 Correct 190 ms 360 KB # of queries: 8657
28 Correct 474 ms 384 KB # of queries: 16956
29 Correct 443 ms 480 KB # of queries: 16937
30 Correct 469 ms 552 KB # of queries: 16956