Submission #538338

#	Time	Username	Problem	Language	Result	Execution time	Memory
538338		Sorting	Carnival (CEOI14_carnival)	C++17	100 / 100	16 ms	340 KiB

carnival

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 150 + 3;

int n;
int t[N], types = 1;
vector<int> v;

int query(const vector<int> &v){
    cout << v.size() << " ";
    for(int x: v)
        cout << x << " ";
    cout << endl;

    int res;
    cin >> res;
    return res;
}

int query(const vector<int> &v, int pos, int x){
    vector<int> v2 = v;
    while(v2.size() > pos)
        v2.pop_back();
    v2.push_back(x);
    return query(v2);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    t[1] = 1;
    v.push_back(1);

    for(int i = 2; i <= n; ++i){
        int l = 0, r = (int)v.size();
        while(l != r){
            int mid = (l + r + 1) >> 1;
            if(query(v, mid, i) == mid + 1)
                l = mid;
            else
                r = mid - 1;
        }
        
        if(l == (int)v.size()){
            v.push_back(i);
            t[i] = ++types;
        }
        else{
            t[i] = t[v[l]];
        }
    }

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

Compilation message (stderr)

carnival.cpp: In function 'int query(const std::vector<int>&, int, int)':
carnival.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     while(v2.size() > pos)
      |           ~~~~~~~~~~^~~~~

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