oj.uz

Submission #422483

# Submission time Handle Problem Language Result Execution time Memory
422483 2021-06-10T07:21:44 Z snasibov05 Carnival (CEOI14_carnival) C++14
100 / 100
 17 ms 328 KB 
#include <iostream>
#include <vector>

using namespace std;

#define pb push_back

int ask(vector<int> v){
    cout << v.size() << " ";
    for (auto x : v) cout << x << " ";
    cout << endl;
    int res; cin >> res;
    return res;
}

void answer(vector<int> ans){
    int n = ans.size() - 1;
    cout << "0 ";
    for (int i = 1; i <= n; ++i){
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    int n; cin >> n;
    vector<int> ans(n+1);
    ans[1] = 1;
    vector<int> unique;
    unique.pb(1);
    for (int i = 2; i <= n; ++i){
        vector<int> v;
        for (auto x : unique) v.pb(x);
        v.pb(i);
        int k = ask(v);
        if (k == unique.size() + 1){
            ans[i] = ans[unique.back()] + 1;
            unique.pb(i);
            continue;
        }

        int l = 0, r = unique.size() - 1;
        while (l < r){
            int m = (l + r) / 2;
            v.clear();
            for (int j = l; j <= m; ++j) {
                v.pb(unique[j]);
            }
            v.pb(i);
            k = ask(v);

            if (k == m - l + 1) r = m;
            else l = m+1;
        }

        ans[i] = ans[unique[l]];
    }

    answer(ans);

    return 0;
}

Compilation message

carnival.cpp: In function 'int main()':
carnival.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if (k == unique.size() + 1){
      |             ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 10 ms 200 KB Output is correct
3 Correct 17 ms 200 KB Output is correct
4 Correct 4 ms 200 KB Output is correct
5 Correct 12 ms 200 KB Output is correct
6 Correct 9 ms 288 KB Output is correct
7 Correct 9 ms 292 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 5 ms 200 KB Output is correct
3 Correct 5 ms 200 KB Output is correct
4 Correct 5 ms 200 KB Output is correct
5 Correct 6 ms 200 KB Output is correct
6 Correct 7 ms 292 KB Output is correct
7 Correct 6 ms 292 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 9 ms 200 KB Output is correct
3 Correct 8 ms 296 KB Output is correct
4 Correct 7 ms 200 KB Output is correct
5 Correct 9 ms 288 KB Output is correct
6 Correct 6 ms 296 KB Output is correct
7 Correct 5 ms 200 KB Output is correct