#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)
{
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 |
456 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
456 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
