oj.uz

Submission #904324

# Submission time Handle Problem Language Result Execution time Memory
904324 2024-01-12T03:39:20 Z nguyen31hoang08minh2003 Turnir (COCI17_turnir) C++17
100 / 100
 241 ms 25888 KB 
#include <bits/stdc++.h>

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

using namespace std;

constexpr int MAX_N = 20;

int N, n;
vector<int> numbers, indices, floorLog2, result;

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N;

    n = 1 << N;

    numbers.resize(n);
    result.resize(n);
    indices.resize(n);
    floorLog2.resize(n + 1);

    for (int i = 2; i <= n; ++i)
        floorLog2[i] = floorLog2[i >> 1] + 1;

    for (int i = 0; i < n; ++i) {
        cin >> numbers[i];
        indices[i] = i;
    }

    sort(indices.begin(), indices.end(), [&](const int &l, const int &r) -> bool {
        return numbers[l] < numbers[r];
    });

    for (int l = 0, r = 0, answer; r < n;) {
        for (; r < n && numbers[indices[l]] == numbers[indices[r]]; ++r);
        answer = N - floorLog2[r];
        for (; l < r; ++l)
            result[indices[l]] = answer;
    }

    for (int i = 0; i < n; ++i)
        cout << result[i] << ' ';
    cout << '\n';

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 7 ms 1116 KB Output is correct
6 Correct 14 ms 1876 KB Output is correct
7 Correct 29 ms 3408 KB Output is correct
8 Correct 54 ms 6228 KB Output is correct
9 Correct 121 ms 13152 KB Output is correct
10 Correct 241 ms 25888 KB Output is correct