Submission #869833

#	Time	Username	Problem	Language	Result	Execution time	Memory
869833		parsadox2	Library (JOI18_library)	C++14	100 / 100	220 ms	1232 KiB

library

#include "library.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e3 + 10;
 
int salam , now;
 
struct block{
	int l , r , sz;
};
vector <block> all_block;
vector <int> adj[N] , ans;
vector <int> M;
 
int check_suf(int ind)
{
	M.clear();
	M.resize(salam , 0);
	M[now - 1] = 1;
	int cnt = 0;
	for(int i = ind / 2 ; i < all_block.size() ; i++)
	{
		cnt += min(all_block[i].sz , 2);
		if(all_block[i].sz == 2)
			cnt--;
		M[all_block[i].l - 1] = 1;
		if(all_block[i].sz != 1)
			M[all_block[i].r - 1] = 1;
	}
	if(ind % 2 == 1)
	{
		if(all_block[ind/2].sz != 1)
		{
			cnt--;
			M[all_block[ind/2].l - 1] = 0;
		}
		if(all_block[ind / 2].sz == 2)
			cnt++;
	}
	return cnt - Query(M) + 1;
}
 
int check_prf(int ind)
{
	M.clear();
	M.resize(salam , 0);
	M[now - 1] = 1;
	int cnt = 0;
	for(int i = 0 ; i <= ind / 2 ; i++)
	{
		cnt += min(all_block[i].sz , 2);
		if(all_block[i].sz == 2)
			cnt--;
		M[all_block[i].l - 1] = 1;
		if(all_block[i].sz != 1)
			M[all_block[i].r - 1] = 1;
	}
	if(ind % 2 == 0)
	{
		if(all_block[ind/2].sz != 1)
		{
			cnt--;
			M[all_block[ind/2].r - 1] = 0;
		}
		if(all_block[ind / 2].sz == 2)
			cnt++;
	}
	return cnt - Query(M) + 1;
}
 
void Add_edge(int a , int b)
{
	adj[a].push_back(b);
	adj[b].push_back(a);
}
 
void Add(int ind)
{
	now = ind;
	int low = -1 , high = (int) all_block.size() * 2;
	while(high - low > 1)
	{
		int mid = (low + high) >> 1;
		if(check_suf(mid) > 0)
			low = mid;
		else
			high = mid;
	}
	if(low == -1)
	{
		all_block.push_back({ind , ind , 1});
		return;
	}
	int pos_fir = low / 2 , fir = all_block[low / 2].l , not_fir = all_block[low / 2].r;
	if(low % 2 == 1)
		swap(fir , not_fir);
	low = -1 , high = (int) all_block.size() * 2;
	while(high - low > 1)
	{
		int mid = (low + high) >> 1;
		if(check_prf(mid) > 0)
			high = mid;
		else
			low = mid;
	}
	int pos_sec = high / 2 , sec = all_block[high / 2].l , not_sec = all_block[high / 2].r;
	if(high % 2 == 1)
		swap(sec , not_sec);
	Add_edge(fir , ind);
	if(pos_fir == pos_sec)
	{
		if(high % 2 == 1)
			all_block[pos_sec].r = ind;
		else
			all_block[pos_sec].l = ind;
		all_block[pos_sec].sz++;
		return;
	}
	Add_edge(sec , ind);
	all_block.erase(all_block.begin() + pos_fir);
	all_block.erase(all_block.begin() + pos_sec);
	all_block.push_back({not_fir , not_sec , 3});
}
 
void Dfs(int v , int p = -1)
{
	ans.push_back(v);
	for(auto u : adj[v])  if(u != p)
		Dfs(u , v);
}
 
void Solve(int n)
{
	salam = n;
	all_block.push_back({1 , 1 , 1});
	for(int i = 2 ; i <= n ; i++)
	{
		Add(i);
	}
	int fir = all_block.back().l;
	Dfs(fir);
	Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'int check_suf(int)':
library.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = ind / 2 ; i < all_block.size() ; i++)
      |                        ~~^~~~~~~~~~~~~~~~~~

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