oj.uz

Submission #418418

# Submission time Handle Problem Language Result Execution time Memory
418418 2021-06-05T11:10:34 Z dolphingarlic Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 566 ms 3764 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, h[1 << 17], at[1 << 17], cp[1 << 17];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < (1 << n); i++) {
        cin >> h[i];
        at[h[i]] = i;
    }

    ll mn = LLONG_MAX;
    string best_seq;
    for (int shift = 0; shift < max(1, n); shift++) {
        int mask = 0;
        ll inv_tot = 0;
        for (int i = 0; i < (1 << n); i++) cp[i] = h[i];
        for (int i = 0; i < n; i++) {
            ll inv_0 = 0, inv_1 = 0;

            for (int j = 0; j < (1 << n); j += 1 << i + 1) {
                int lptr = j, rptr = j + (1 << i), l_used = 0, r_used = 0;
                vector<int> sorted;
                while (lptr < j + (1 << i) && rptr < j + (1 << i + 1)) {
                    if (cp[lptr] > cp[rptr]) {
                        inv_1 += l_used;
                        sorted.push_back(cp[rptr]);
                        rptr++, r_used++;
                    } else {
                        inv_0 += r_used;
                        sorted.push_back(cp[lptr]);
                        lptr++, l_used++;
                    }
                }
                while (lptr < j + (1 << i)) {
                    inv_0 += r_used;
                    sorted.push_back(cp[lptr]);
                    lptr++, l_used++;
                }
                while (rptr < j + (1 << i + 1)) {
                    inv_1 += l_used;
                    sorted.push_back(cp[rptr]);
                    rptr++, r_used++;
                }
                for (int k = 0; k < (1 << i + 1); k++) cp[j + k] = sorted[k];
            }

            if (inv_0 > inv_1) mask += 1 << i;
            inv_tot += min(inv_0, inv_1);
        }

        if (inv_tot < mn) {
            string seq;
            for (int i = 0; i < shift; i++) seq += "2";
            for (int i = 0; i < n; i++) {
                seq += "2";
                if (mask & (1 << i)) seq += "1";
            }
            mn = inv_tot;
            best_seq = seq;
        }

        for (int i = 0; i < (1 << n); i++) {
            at[i] = (at[i] >> 1) + ((at[i] & 1) << n - 1);
            h[at[i]] = i;
        }
    }
    cout << mn << '\n' << best_seq;
    return 0;
}

Compilation message

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:24:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   24 |             for (int j = 0; j < (1 << n); j += 1 << i + 1) {
      |                                                     ~~^~~
cheerleaders.cpp:27:66: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   27 |                 while (lptr < j + (1 << i) && rptr < j + (1 << i + 1)) {
      |                                                                ~~^~~
cheerleaders.cpp:43:43: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   43 |                 while (rptr < j + (1 << i + 1)) {
      |                                         ~~^~~
cheerleaders.cpp:48:45: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   48 |                 for (int k = 0; k < (1 << i + 1); k++) cp[j + k] = sorted[k];
      |                                           ~~^~~
cheerleaders.cpp:67:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |             at[i] = (at[i] >> 1) + ((at[i] & 1) << n - 1);
      |                                                    ~~^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct!
2 Correct 0 ms 204 KB Correct!
3 Correct 0 ms 204 KB Correct!
4 Correct 0 ms 204 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct!
2 Correct 1 ms 204 KB Correct!
3 Correct 1 ms 204 KB Correct!
4 Correct 1 ms 204 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Correct!
2 Correct 5 ms 332 KB Correct!
3 Correct 6 ms 368 KB Correct!
4 Correct 5 ms 368 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 964 KB Correct!
2 Correct 78 ms 976 KB Correct!
3 Correct 173 ms 1712 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 2976 KB Correct!
2 Correct 398 ms 2908 KB Correct!
3 Correct 564 ms 2864 KB Correct!
4 Correct 566 ms 3564 KB Correct!
5 Correct 558 ms 3764 KB Correct!