oj.uz

Submission #820499

# Submission time Handle Problem Language Result Execution time Memory
820499 2023-08-11T04:30:42 Z Faisal_Saqib Library (JOI18_library) C++17
19 / 100
 213 ms 428 KB 
#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include "library.h"
using namespace std;
// void Solve(int N);
int par[3000];
int ans1[3000];
bool vis[3000];
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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 336 KB # of queries: 5923
2 Correct 56 ms 312 KB # of queries: 5566
3 Correct 46 ms 312 KB # of queries: 5773
4 Correct 87 ms 304 KB # of queries: 9087
5 Correct 63 ms 336 KB # of queries: 7563
6 Correct 85 ms 428 KB # of queries: 6863
7 Correct 75 ms 316 KB # of queries: 7487
8 Correct 62 ms 328 KB # of queries: 7866
9 Correct 54 ms 320 KB # of queries: 5770
10 Correct 41 ms 428 KB # of queries: 4066
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 0 ms 208 KB # of queries: 9
15 Correct 1 ms 304 KB # of queries: 124
16 Correct 3 ms 208 KB # of queries: 312

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 336 KB # of queries: 5923
2 Correct 56 ms 312 KB # of queries: 5566
3 Correct 46 ms 312 KB # of queries: 5773
4 Correct 87 ms 304 KB # of queries: 9087
5 Correct 63 ms 336 KB # of queries: 7563
6 Correct 85 ms 428 KB # of queries: 6863
7 Correct 75 ms 316 KB # of queries: 7487
8 Correct 62 ms 328 KB # of queries: 7866
9 Correct 54 ms 320 KB # of queries: 5770
10 Correct 41 ms 428 KB # of queries: 4066
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 0 ms 208 KB # of queries: 9
15 Correct 1 ms 304 KB # of queries: 124
16 Correct 3 ms 208 KB # of queries: 312
17 Runtime error 213 ms 404 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -