oj.uz

Submission #869833

# Submission time Handle Problem Language Result Execution time Memory
869833 2023-11-05T19:51:39 Z parsadox2 Library (JOI18_library) C++14
100 / 100
 220 ms 1232 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB # of queries: 1829
2 Correct 16 ms 472 KB # of queries: 1845
3 Correct 19 ms 708 KB # of queries: 1931
4 Correct 16 ms 716 KB # of queries: 1972
5 Correct 19 ms 716 KB # of queries: 1958
6 Correct 18 ms 716 KB # of queries: 1951
7 Correct 16 ms 460 KB # of queries: 1949
8 Correct 19 ms 716 KB # of queries: 1864
9 Correct 17 ms 692 KB # of queries: 1927
10 Correct 11 ms 464 KB # of queries: 1107
11 Correct 0 ms 340 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 3
13 Correct 0 ms 344 KB # of queries: 7
14 Correct 1 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 64
16 Correct 1 ms 344 KB # of queries: 155

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB # of queries: 1829
2 Correct 16 ms 472 KB # of queries: 1845
3 Correct 19 ms 708 KB # of queries: 1931
4 Correct 16 ms 716 KB # of queries: 1972
5 Correct 19 ms 716 KB # of queries: 1958
6 Correct 18 ms 716 KB # of queries: 1951
7 Correct 16 ms 460 KB # of queries: 1949
8 Correct 19 ms 716 KB # of queries: 1864
9 Correct 17 ms 692 KB # of queries: 1927
10 Correct 11 ms 464 KB # of queries: 1107
11 Correct 0 ms 340 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 3
13 Correct 0 ms 344 KB # of queries: 7
14 Correct 1 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 64
16 Correct 1 ms 344 KB # of queries: 155
17 Correct 205 ms 1232 KB # of queries: 13487
18 Correct 200 ms 716 KB # of queries: 13311
19 Correct 218 ms 728 KB # of queries: 13275
20 Correct 199 ms 976 KB # of queries: 12444
21 Correct 169 ms 700 KB # of queries: 11798
22 Correct 216 ms 732 KB # of queries: 13398
23 Correct 220 ms 1220 KB # of queries: 13439
24 Correct 76 ms 708 KB # of queries: 6115
25 Correct 216 ms 728 KB # of queries: 13128
26 Correct 204 ms 716 KB # of queries: 12225
27 Correct 67 ms 708 KB # of queries: 6018
28 Correct 44 ms 720 KB # of queries: 2997
29 Correct 54 ms 952 KB # of queries: 2994
30 Correct 56 ms 960 KB # of queries: 2997