oj.uz

Submission #908781

# Submission time Handle Problem Language Result Execution time Memory
908781 2024-01-16T20:42:30 Z tvladm2009 Carnival (CEOI14_carnival) C++17
100 / 100
 16 ms 1208 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int n;
 
//vector<int> HIDDEN = {1, 2, 1, 3, 2};
 
int ask(vector<int> guys) {
    cout << guys.size() << " ";
    for (auto i : guys) cout << i << " ";
    /**
    cout << endl;
    set<int> s;
    for (auto i : guys) s.insert(HIDDEN[i - 1]);
    return s.size();
    **/
    int res;
    cin >> res;
    return res;
}
 
int main() {
    cin >> n;
    vector<int> sol(n + 1);
    int cnt = 1;
    sol[1] = 1;
    vector<int> full;
    vector<int> pref;
    full.push_back(1);
    pref.push_back(1);
    for (int i = 2; i <= n; ++i) {
        int x = ask(full);
        full.push_back(i);
        if (ask(full) == x + 1) {
            sol[i] = ++cnt;
            pref.push_back(cnt);
            continue;
        }
        int l = 1, r = i - 1, ans = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            vector<int> query;
            query.push_back(i);
            for (int j = 1; j <= m; ++j) {
                query.push_back(j);
            }
            if (ask(query) == pref[m - 1] + 1) {
                l = m + 1;
                ans = m;
            } else {
                r = m - 1;
            }
        }
        sol[i] = sol[ans + 1];
        pref.push_back(cnt);
    }
    cout << "0 ";
    for (int i = 1; i <= n; ++i) cout << sol[i] << " ";
    cout << endl;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 696 KB Output is correct
2 Correct 6 ms 700 KB Output is correct
3 Correct 5 ms 700 KB Output is correct
4 Correct 3 ms 952 KB Output is correct
5 Correct 6 ms 944 KB Output is correct
6 Correct 7 ms 700 KB Output is correct
7 Correct 5 ms 704 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 696 KB Output is correct
2 Correct 6 ms 696 KB Output is correct
3 Correct 3 ms 688 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 6 ms 448 KB Output is correct
6 Correct 6 ms 1208 KB Output is correct
7 Correct 16 ms 948 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 700 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 6 ms 952 KB Output is correct
4 Correct 3 ms 948 KB Output is correct
5 Correct 5 ms 440 KB Output is correct
6 Correct 6 ms 688 KB Output is correct
7 Correct 6 ms 700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 944 KB Output is correct
2 Correct 9 ms 432 KB Output is correct
3 Correct 4 ms 692 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 5 ms 696 KB Output is correct
6 Correct 5 ms 696 KB Output is correct
7 Correct 6 ms 948 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 692 KB Output is correct
2 Correct 7 ms 692 KB Output is correct
3 Correct 5 ms 700 KB Output is correct
4 Correct 5 ms 432 KB Output is correct
5 Correct 4 ms 692 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 4 ms 948 KB Output is correct