Submission #433171

#	Time	Username	Problem	Language	Result	Execution time	Memory
433171		apotosaurus	Carnival (CEOI14_carnival)	C++11	0 / 100	9 ms	296 KiB

carnival

#include <bits/stdc++.h>

using namespace std;

#define DEBUG false
#define cdbg if (!DEBUG) {} else cerr

// #define int long long

// #define INFILE "carnival.in"
// #define OUTFILE "carnival.out"

int N;
vector<int> reps;
vector<int> unassigned;
vector<int> res;
int curCostume = 0;

void readInput(){
    cin >> N;
    res.resize(N);
}

//checks if the closed interval [0,x] has reps[i] = it for some i in the interval
bool works (int x, int it){
    cout << x+2 << " ";
    for (int i = 0; i <= x; i++){
        cout << reps[i] << " ";
    }
    cout << it << endl;
    int tmp;
    cin >> tmp;
    cdbg << "\tWorks: " << (tmp == x+1) << endl;
    return (tmp == x+1);
}

//looking for the smallest x such that for all 0<=i<=x, reps[i] = it
int search(int it){
    int lb = 0;
    int ub = reps.size()-1;
    //lb is largest such that nothing below it inclusive contains it
    //ub is the smallest such that something below it inclusive contains it
    while (lb < ub){
        int mid = (lb + ub) / 2;
        if (works(mid, it)){
            ub = mid;
        }
        else{
            lb = mid + 1;
        }
    }
    cdbg << lb << endl;
    return lb;
}

void solve(){
    reps.push_back(1);
    res[0] = reps.size();
    for (int i = 1; i < N; i++){
        cout << (reps.size() + 1) << " ";
        for (int j = 0; j < reps.size(); j++){
            cout << reps[j] << " ";
        }
        cout << i+1 << endl;
        int tmp;
        cin >> tmp;
        if (tmp == reps.size()){
            unassigned.push_back(i+1);
        }
        else{
            reps.push_back(i+1);
            res[i] = reps.size();
        }
    }
    //binary search now
    for (auto it:unassigned){
        res[it-1] = res[search(it)];
    }
    cout << 0 << " ";
    for (int i = 0; i < N; i++){
        cout << res[i] << " ";
    }
    cout << endl;
}

// main(){
int main(){    
    // freopen(INFILE, "r", stdin); // redirects standard input
    // freopen(OUTFILE, "w", stdout); // redirects standard output
    
    readInput();
    solve();

    return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'void solve()':
carnival.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int j = 0; j < reps.size(); j++){
      |                         ~~^~~~~~~~~~~~~
carnival.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         if (tmp == reps.size()){
      |             ~~~~^~~~~~~~~~~~~~

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