oj.uz

Submission #247960

# Submission time Handle Problem Language Result Execution time Memory
247960 2020-07-12T06:58:46 Z VEGAnn Turnir (COCI17_turnir) C++14
100 / 100
 411 ms 17260 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, a[(1 << N)], ans[(1 << N)], nm[(1 << N)];

bool cmp(int _x, int _y){
    return a[_x] < a[_y];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < (1 << n); i++) {
        cin >> a[i];
        nm[i] = i;
    }

    sort(nm, nm + (1 << n), cmp);

    for (int it = (1 << n) - 1; it >= 0; ){
        int i = nm[it];

        int cnt = it + 1;

        int po = 0;

        while ((1 << (po + 1)) <= cnt)
            po++;

        int j = it;

        while (j >= 0 && a[nm[j]] == a[i]){
            ans[nm[j]] = n - po;
            j--;
        }

        it = j;
    }

    for (int i = 0; i < (1 << n); i++)
        cout << ans[i] << " ";

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 9 ms 1024 KB Output is correct
6 Correct 21 ms 1656 KB Output is correct
7 Correct 42 ms 2936 KB Output is correct
8 Correct 77 ms 5240 KB Output is correct
9 Correct 195 ms 10488 KB Output is correct
10 Correct 411 ms 17260 KB Output is correct