oj.uz

Submission #433436

# Submission time Handle Problem Language Result Execution time Memory
433436 2021-06-19T19:39:50 Z apotosaurus Carnival (CEOI14_carnival) C++11
100 / 100
 12 ms 296 KB 
#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
//returns the index in reps
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){
        int idx = search(it);
        int person = reps[idx];
        res[it-1] = res[person-1];
        cdbg << "Found: " << it << ": " << idx << ", " << person << ", " << res[person-1] << endl;
    }
    cout << 0;
    for (int i = 0; i < N; i++){
        cout << " " << res[i];
    }
    cout << endl;
    return;
}

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

    return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 200 KB Output is correct
2 Correct 9 ms 292 KB Output is correct
3 Correct 6 ms 200 KB Output is correct
4 Correct 4 ms 288 KB Output is correct
5 Correct 6 ms 200 KB Output is correct
6 Correct 2 ms 200 KB Output is correct
7 Correct 8 ms 200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 200 KB Output is correct
2 Correct 10 ms 200 KB Output is correct
3 Correct 5 ms 200 KB Output is correct
4 Correct 3 ms 200 KB Output is correct
5 Correct 9 ms 200 KB Output is correct
6 Correct 9 ms 284 KB Output is correct
7 Correct 6 ms 200 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 288 KB Output is correct
2 Correct 6 ms 200 KB Output is correct
3 Correct 12 ms 200 KB Output is correct
4 Correct 4 ms 200 KB Output is correct
5 Correct 10 ms 200 KB Output is correct
6 Correct 10 ms 284 KB Output is correct
7 Correct 10 ms 200 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 200 KB Output is correct
2 Correct 6 ms 200 KB Output is correct
3 Correct 7 ms 200 KB Output is correct
4 Correct 4 ms 200 KB Output is correct
5 Correct 10 ms 200 KB Output is correct
6 Correct 7 ms 200 KB Output is correct
7 Correct 9 ms 200 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Output is correct
2 Correct 6 ms 200 KB Output is correct
3 Correct 8 ms 200 KB Output is correct
4 Correct 7 ms 200 KB Output is correct
5 Correct 8 ms 200 KB Output is correct
6 Correct 6 ms 200 KB Output is correct
7 Correct 5 ms 296 KB Output is correct