Submission #403335

#	Time	Username	Problem	Language	Result	Execution time	Memory
403335		rainliofficial	Carnival (CEOI14_carnival)	C++17	100 / 100	12 ms	288 KiB

carnival

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

/*
Ideas + Goals
- Find out how many unique costumes there are and store them
- Then, look through all of the custumes (that are repeated (so not detected in our first search of unique cpstumes))
- Use binary search (divide and conquer) the list of unique costumes to narrow down on WHICH costomes I repeated with

Implmention details
- To find out how many unique customes, we can't only check pairs of people. What if we just start from the beginning, and expand our window by adding more
people into our query. This keeps the previous results (total number of repeats/uniques we have seen), and checks it against the newly added element. 
Unlike checking pairs, we don't know whether we have seem that costume before, so we can't determine if it is a repeat globally, we can only determine if it
repeats with that pair. We start from the beginning because we only really care about the first time a costume shows up, as that tells us the totla number
of unique customes, and we will store that in a set call "all".
- To check the reamining costumes (the ones not deems as the first of a unique costume), we will need to use binary search. Do binary search on the list we created
called "all", which has all of the unique costumes. We divide the list into halves everytime, and checks the current element against it. Since we know all the
elems in the set are unique, if plus the additional element, the query gives a size of mid+1, we know that the current element DOES NOT repeat with any of the
elems in that half. So it must repeat in the other half, so we increament/decrament high/low accordingly.
*/

vector<int> all;

int main(){
    int n;
    cin >> n;
    int ans[n];
    memset(ans, 0, n*sizeof(ans[0]));
    int g = 1;
    int prev = 0;
    for (int i=1; i<=n; i++){
        // Pass through all the elements by adding new element into our query, to check if it has appeard before (if not, it is new, add into the "all" list)
        cout << i << " ";
        for (int j=1; j<=i; j++){
            cout << j << " ";
        }
        cout << "\n";
        fflush(stdin);
        int res = 0;
        cin >> res;
        if (res > prev){
            // This element is new, as we have an additional costume compared to before
            all.push_back(i);
            ans[i-1] = g++;
        }
        prev = res;
    }   
    // We have filled in our ans[] for all the FIRST appearences of costumes. The onces left are repeats, so we need to determine which costume it repeats with
    for (int i=1; i<=n; i++){
        if (ans[i-1] == 0){
            // Do binary search to divide and conquer the "all" list
            int low = 0; int high = all.size()-1;
            while (low < high){
                int mid = (low + high)/2;
                cout << mid-low+2; // Mid is 0 base indexed, so mid+1 for number of elements in the "all" list, and +1 for our current element. Totoal m+2 elems printed
                for (int j=low; j<=mid; j++){
                    // We check everytime from 0-mid. If this section does not contain repeats, we will extend this section further right (in hope that the costumes
                    // we expanded into our query will contain the repeat that we are looking for)
                    // If 0-mid does contain our repeat, we can decrease our high to mid. There is no point looking at the other section anymore.
                    cout << " " << all[j];
                }
                cout << " " << i << "\n";
                fflush(stdin);
                int res = 0;
                cin >> res;
                if (res == mid-low+2){
                    // Current element does not repeat with any elements in this section of the list (low to mid)
                    low = mid+1;
                }else{
                    // Low to mid does contain a repeat of the current element
                    high = mid;
                }
            }
            // Now we should have low = index of the repeated element in th all[]
            ans[i-1] = ans[all[low]-1]; // Then since I am repeated with all[low] my ans = ans[all[low]]
        }
    }
    cout << "0 ";
    for (int i : ans){
        cout << i << " ";
    }
    return 0;
}

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