Submission #1324106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324106		sh_qaxxorov_571	사육제 (CEOI14_carnival)	C++20	100 / 100	3 ms	428 KiB

carnival

#include <iostream>
#include <vector>

using namespace std;

/**
 * CEOI 2014 - Carnival
 * So'rovlar soni: O(N * log N)
 * N = 150 uchun taxminan 150 * 8 = 1200 so'rov, bu 3500 limitidan ancha kam.
 */

int ask(const vector<int>& v) {
    if (v.empty()) return 0;
    cout << v.size();
    for (int x : v) cout << " " << x;
    cout << endl;
    int res;
    cin >> res;
    return res;
}

int main() {
    int N;
    cin >> N;

    vector<int> costume_id(N + 1);
    vector<int> unique_reps; // Har bir turning vakillari (do'st raqamlari)

    costume_id[1] = 1;
    unique_reps.push_back(1);
    int current_max_id = 1;

    for (int i = 2; i <= N; i++) {
        // Avval i-do'st barcha vakillar bilan birga yangi turmi yoki yo'qligini tekshiramiz
        vector<int> query = unique_reps;
        query.push_back(i);
        
        if (ask(query) > (int)unique_reps.size()) {
            // Yangi kostyum turi
            current_max_id++;
            costume_id[i] = current_max_id;
            unique_reps.push_back(i);
        } else {
            // Avvalgi kostyumlardan biri bilan bir xil, Binary Search boshlaymiz
            int low = 0, high = (int)unique_reps.size() - 1;
            int found_idx = 0;
            
            while (low <= high) {
                int mid = (low + high) / 2;
                vector<int> sub_query;
                for (int j = 0; j <= mid; j++) sub_query.push_back(unique_reps[j]);
                int res1 = (int)sub_query.size();
                sub_query.push_back(i);
                int res2 = ask(sub_query);
                
                if (res1 == res2) {
                    found_idx = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            costume_id[i] = costume_id[unique_reps[found_idx]];
        }
    }

    // Natijani chiqarish
    cout << 0;
    for (int i = 1; i <= N; i++) cout << " " << costume_id[i];
    cout << endl;

    return 0;
}

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