oj.uz

Submission #749953

# Submission time Handle Problem Language Result Execution time Memory
749953 2023-05-29T02:15:49 Z vjudge1 Carnival (CEOI14_carnival) C++17
100 / 100
 11 ms 336 KB 
/*
#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+1 << " ";
    }
    return 0;
}

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)
      |             ~~~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 208 KB Output is correct
2 Correct 8 ms 336 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 8 ms 208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 208 KB Output is correct
2 Correct 10 ms 332 KB Output is correct
3 Correct 4 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 8 ms 208 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Correct 9 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 8 ms 332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Correct 7 ms 336 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 6 ms 336 KB Output is correct
7 Correct 8 ms 328 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 11 ms 208 KB Output is correct
3 Correct 10 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 6 ms 208 KB Output is correct
7 Correct 7 ms 336 KB Output is correct