/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int ask(vector<int> &a)
{
cout << a.size() << " ";
for (auto v : a)
{
cout << v << " ";
}
cout << endl;
int d;
cin >> d;
return d;
}
int pa[maxn];
vector<int> get(vector<int> &a, int l, int r)
{
vector<int> cac;
for (int i = l; i <= r; i++)
{
cac.pb(a[i]);
}
return cac;
}
vector<int> dnc(int l, int r)
{
if (l == r)
{
vector<int> d;
d.pb(l);
return d;
}
int mid = (l + r) / 2;
vector<int> k1 = dnc(l, mid);
vector<int> k2 = dnc(mid + 1, r);
vector<int> id = k1;
for (auto v : k2)
{
int l = 0;
int r = k1.size() - 1;
vector<int> d = k1;
d.pb(v);
if (ask(d) == k1.size()+1)
{
id.pb(v);
}
else
{
int ans = -1;
while (l <= r)
{
int mid = (l + r) / 2;
vector<int> k = get(k1, l, mid);
k.pb(v);
if (ask(k) == mid-l+1)
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
pa[v] = k1[ans];
}
}
return id;
}
int fin(int x)
{
if (x == pa[x])
return x;
return pa[x] = fin(pa[x]);
}
signed main()
{
cin.tie(0), cout.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
pa[i] = i;
}
vector<int> an = dnc(1, n);
cout << "0 ";
for (int i = 1; i <= n; i++)
{
int k = fin(i);
int d = lower_bound(an.begin(), an.end(), k) - an.begin();
cout << d << " ";
}
}
Compilation message
carnival.cpp: In function 'std::vector<int> dnc(int, int)':
carnival.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if (ask(d) == k1.size()+1)
| ~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
208 KB |
Integer 0 violates the range [1, 11] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
208 KB |
Integer 0 violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
208 KB |
Integer 0 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
208 KB |
Integer 0 violates the range [1, 4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
336 KB |
Integer 0 violates the range [1, 2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
