제출 #1309545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309545		HishamAlshehri	사육제 (CEOI14_carnival)	C++20	100 / 100	3 ms	452 KiB

carnival

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
 
#define int long long
#define mod 1000000007
#define base 7001
#define base2 757
#define F first
#define S second
// #define pi acos(-1)
#define double long double
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,sse3,sse4,avx")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int maxn = 1000005;
const int N = 1 << (int)(ceil(log2(maxn)));

int n, a[maxn], par[maxn];

int query(int i, vector<int> cur) {
    cout << cur.size() + 1 << ' ';
    for (int v : cur) cout << v << ' ';
    cout << i << endl;
    
    int x; cin >> x;
    return x;
}

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    
    vector<int> cur;
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        int x = query(i, cur);
        if (x > cur.size()) {
            cur.push_back(i);
            par[i] = cnt++;
            continue;
        }

        int l = 0, r = cur.size() - 1, ans = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            
            vector<int> t;
            for (int j = 0; j <= m; j++) t.push_back(cur[j]);
            int y = query(i, t);

            if (y == t.size()) {
                r = m - 1;
                ans = m;
            }
            else l = m + 1;
        }
        // cout << ans << '\n';
        par[i] = par[cur[ans]];
    }

    cout << "0 ";
    for (int i = 0; i < n; i++) cout << par[i + 1] << " ";
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20