oj.uz

Submission #1104994

# Submission time Handle Problem Language Result Execution time Memory
1104994 2024-10-25T05:19:36 Z huyngo Carnival (CEOI14_carnival) C++17
100 / 100
 16 ms 4724 KB 
#include <bits/stdc++.h>  
using namespace std;
using ll = long long;
using i64 = long long;
void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char* x) { cerr << '"' << x << '"'; } void __print(const string& x) { cerr << '"' << x << '"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template<typename T, typename V> void __print(const pair<T, V>& x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; } template<typename T> void __print(const T& x) { int f = 0; cerr << '{'; for (auto& i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#define ln "\n"
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define ar array
int Bit(int mask, int b) { return (mask >> b) & 1; }
const ll base = 311, MOD = 998244353, M = 1e9 + 7, INF = 1e18;

const int mxN = 1e6 + 5;
int n;
int tr[mxN], del[mxN];

int32_t main() {
    cin >> n;
    memset(del, 0, sizeof del);

    auto uniq = [&](int l, int r) -> bool {
        int num = 0;
        rep(i, l, r) if (!del[i])
            ++num;
        cout << num << " ";
        rep(i, l, r) if (!del[i]) cout << i << ' ';
        cout << endl;
        int x; cin >> x;
        return x == num;
        };

    while (true) {
        int l = 1, r = n, f = n + 10;
        while (l <= r) {
            int m = (l + r) / 2;
            if (!uniq(1, m)) {
                f = min(f, m);
                r = m - 1;
            }
            else
                l = m + 1;
        }
        if (f == n + 10) break;
        l = 1, r = f;
        int g = 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (!uniq(m, f)) {
                g = max(g, m);
                l = m + 1;
            }
            else
                r = m - 1;
        }
        tr[f] = g;
        del[f] = 1;
    }

    int used = 0;
    vector<int> ans(n + 1);
    rep(i, 1, n)
        if (tr[i] == 0)
            ans[i] = ++used;
        else
            ans[i] = ans[tr[i]];

    cout << 0 << " ";
    rep(i, 1, n)
        cout << ans[i] << ' ';
    cout << endl;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4688 KB Output is correct
2 Correct 11 ms 4688 KB Output is correct
3 Correct 8 ms 4688 KB Output is correct
4 Correct 2 ms 4688 KB Output is correct
5 Correct 11 ms 4688 KB Output is correct
6 Correct 12 ms 4688 KB Output is correct
7 Correct 12 ms 4688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4688 KB Output is correct
2 Correct 14 ms 4688 KB Output is correct
3 Correct 6 ms 4688 KB Output is correct
4 Correct 4 ms 4688 KB Output is correct
5 Correct 14 ms 4688 KB Output is correct
6 Correct 13 ms 4688 KB Output is correct
7 Correct 13 ms 4688 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4688 KB Output is correct
2 Correct 14 ms 4688 KB Output is correct
3 Correct 11 ms 4688 KB Output is correct
4 Correct 2 ms 4688 KB Output is correct
5 Correct 12 ms 4724 KB Output is correct
6 Correct 12 ms 4688 KB Output is correct
7 Correct 11 ms 4688 KB Output is correct

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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