Submission #820510

#	Time	Username	Problem	Language	Result	Execution time	Memory
820510		Faisal_Saqib	Library (JOI18_library)	C++17	19 / 100	219 ms	656 KiB

library

#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include "library.h"
using namespace std;
// void Solve(int N);
int par[10000];
int ans1[10000];
bool vis[10000];
int n;
map<int,vector<int>> ma;
int query(vector<int>& a,bool p=0)
{
	// cout<<"for ";
	// for(auto i:a)
	// {
	// 	cout<<i<<' ';
	// }
	// cout<<endl;
	vector<int> que(n);
	for(auto i:a)
	{
		que[i-1]=1;
	}
	return Query(que);
}
int get(int x)
{
	if(x==par[x])
	{
		return x;
	}
	return par[x]=get(par[x]);
}
void join(int a,int b)
{
	a=get(a);
	b=get(b);
	par[a]=b;
}
int check(vector<int> a,int b)
{
	// cout<<"reason "<<b<<endl;
	a.push_back(b);
	int x=query(a,1);
	// cout<<"answer "<<x<<endl;
	if(x==a.size())
	{
		return 0;	
	}
	else if(x==(a.size()-1))
	{
		return 1;
	}
	else
	{
		return 2;
	}
}
void find(vector<int> a,int x,int mn)
{
	if(mn==0 or a.size()==0)
	{
		return;
	}
	if(a.size()==1)
	{
		// cout<<"Book "<<x<<' '<<" adj to ";;
		for(int i=0;i<1;i++)
		{
			// cout<<a[i]<<' ';
			ma[a[i]].push_back(x);
			ma[x].push_back(a[i]);
		}
		// cout<<endl;
		return;
	}
	int mid=(a.size()/2);
	vector<int> fh,sh;
	for(int i=0;i<a.size();i++)
	{
		if(i<mid)
		{
			fh.push_back(a[i]);
		}
		else
		{
			sh.push_back(a[i]);
		}
	}
	find(fh,x,check(fh,x));
	find(sh,x,check(sh,x));
}
int cur=1;
void dfs(int x)
{
	vis[x]=1;
	ans1[cur]=x;
	// cout<<x<<' '<<cur<<endl;
	cur++;
	for(auto y:ma[x])
	{
		// cout<<"adj "<<y<<' '<<x<<endl;
		if(!vis[y])
		{
			dfs(y);
		}
	}
}
void Solve(int opas)
{
	n=opas;
	// cout<<"Hello"<<endl;
	vector<int> h;
	h.push_back(1);
	for(int i=2;i<=n;i++)
	{
		h.push_back(i);
		int x=query(h);
		// cout<<"Now"<<endl;
		if(x==h.size())
		{
			// cout<<i<<' '<<"Dif"<<endl;
		}
		else if(x==(h.size()-1))
		{
			h.pop_back();
			find(h,i,1);
			h.push_back(i);
		}
		else
		{
			h.pop_back();
			find(h,i,2);
			h.push_back(i);
		}
	}
	vector<int> ans(n);
	for(int i=1;i<=n;i++)
	{
		if(ma[i].size()==1 and !vis[i])
		{
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			ans1[cur]=i;
			cur++;
		}
	}
	// cout<<"Hello"<<endl;
	for(int i=1;i<=n;i++)
	{
		// cout<<ans1[i]<<' ';
		ans[i-1]=ans1[i];
	}
	// cout<<endl;
	Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'int check(std::vector<int>, int)':
library.cpp:49:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  if(x==a.size())
      |     ~^~~~~~~~~~
library.cpp:53:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  else if(x==(a.size()-1))
      |          ~^~~~~~~~~~~~~~
library.cpp: In function 'void find(std::vector<int>, int, int)':
library.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i=0;i<a.size();i++)
      |              ~^~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:123:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   if(x==h.size())
      |      ~^~~~~~~~~~
library.cpp:127:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   else if(x==(h.size()-1))
      |           ~^~~~~~~~~~~~~~

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