Mistrz Programowania

Mistrz Programowania 2025 runda 2 poziom e
Tagi: interaktywne
Autor zadania: XV Zhautykov Olympiad on Mathematics, Physics and Informatics
Treść

Omówienie zadania Park rozrywki

Oryginalna treść: https://oj.uz/problem/view/IZhO19_xoractive

Zapytajmy się najpierw jaka liczba stoi na pozycji $1$. Teraz zauważmy, że jeżeli zadamy drugi rodzaj pytania o zbiór $A$, który zawiera $1$, a następnie zadamy to samo pytanie, ale bez $1$, to dowiemy się dokładnie jakie liczby składają się na ten zbiór indeksów.

Przykład (Liczby poniżej to indeksy, a nie wartości):

Czyli umiemy w 2 operacje znaleźć jakie liczby są na dowolnym podzbiorze indeksów, ale nadal nie wiemy nic o ich kolejności. Aby ją poznać, rozłożymy indeksy na zapis binarny i zadamy następujące pytania:

i tak dalej. Dla $i$-tego pytania, dla każdej z liczb którą otrzymamy zapisujemy, że jej indeks ma $1$ na $i$-tej pozycji w jego zapisie binarnym, pozostałe liczby będą miały tam $0$. Po zadaniu wszystkich pytań, będziemy znali wszystkie liczby w ciągu wraz z ich indeksami.

Pytań maksymalnie zadamy $7 \cdot 2 + 1 = 15$:

Przykładowe implementacje

C++

#include <bits/stdc++.h>
using namespace std;

multiset<int> get_subset(vector <int> ids) {
    cout << "2 " << ids.size() + 1 << " 1";
    for (int i : ids)
        cout << " " << i;
    cout << endl;

    multiset <int> subset;
    for (size_t i = 0; i < (ids.size() + 1) * (ids.size() + 1); i++) {
        int x;
        cin >> x;
        subset.insert(x);
    }

    cout << "2 " << ids.size();
    for (int i : ids)
        cout << " " << i;
    cout << endl;

    for (size_t i = 0; i < ids.size() * ids.size(); i++) {
        int x;
        cin >> x;
        subset.erase(subset.find(x));
    }
    return subset;
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    
    cout << "1 1" << endl;
    cin >> v[0];

    map<int, int> mp;
    for (int i = 0; i < 7; i++) {
        multiset<int> subset;
        vector <int> subset_ids;
        for (int j = 1; j < n; j++)
            if ((j & (1 << i)))
                subset_ids.push_back(j + 1);
        if (subset_ids.empty())
            continue;
        subset = get_subset(subset_ids);

        for (auto e : subset)
            mp[e] |= (1 << i);
    }

    for (auto e : mp)
        if (e.first)
            v[e.second] = e.first ^ v[0];

    cout << "3";
    for (int i : v)
        cout << " " << i;
    cout << endl;
    return 0;
}

Uwagi