Submission #869826

# Submission time Handle Problem Language Result Execution time Memory
869826 2023-11-05T19:40:17 Z parsadox2 Library (JOI18_library) C++14
0 / 100
0 ms 452 KB
#include <bits/stdc++.h>
#include <library.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)
{
	cout << "suf " << ind << endl;
	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)
{
	cout << "prf " << ind << endl;
	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);
		cout << i << " : " << endl;
		for(auto u : all_block)
			cout << u.l << " " << u.r << " " << u.sz << endl;
	}
	int fir = all_block.back().l;
	Dfs(fir);
	Answer(ans);
}

Compilation message

library.cpp: In function 'int check_suf(int)':
library.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i = ind / 2 ; i < all_block.size() ; i++)
      |                        ~~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 452 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 452 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -