Submission #734927

#	Time	Username	Problem	Language	Result	Execution time	Memory
734927		keta_tsimakuridze	Cheerleaders (info1cup20_cheerleaders)	C++14	0 / 100	1033 ms	27748 KiB

cheerleaders

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define _ pair<ll,string>
#define pii pair<int,int>
using namespace std;
const int N = (1 << 17), mod = 1e9 + 7; // !
int n, t[N], h[N], P[N];
vector<int> v[N];
void upd(int x, int val) {
    ++x;
    for(x; x >= 1; x -= x & (-x)) t[x] += val;
}
int get(int x) {
    ++x;
    int ans = 0;
    for(x; x <= (1 << n); x += x & (-x)) ans += t[x];
    return ans;
}
_ solve(int n) {
    ll CN = 1e15;
    string S = "";
    for(int mx = 0; mx < n; mx++) {
        ll cn = 0;
        string s = "";
        for(int i = 0; i <= mx; i++) {
            for(int j = 0; j < (1 << n); j++) v[(P[j] & ((1 << (mx + 1)) - 1)) - (P[j] & ((1 << (i + 1)) - 1))].push_back(P[j]);
            ll c1 = 0, c2 = 0, C = 0;
            for(int j = 0; j < (1 << n); j++) {
                vector<int> b[2];
                for(int k = 0; k < v[j].size(); k++) {
                    b[(v[j][k] & (1 << i)) > 0].push_back(v[j][k]);
                }
                v[j].clear();
                if(i == 0) {
                    for(int t = 0; t < 2; t++) {
                        for(int k = 0; k < b[t].size(); k++) {
                            C += get(b[t][k]);
                            upd(b[t][k], 1);
                        }
                        for(int k = 0; k < b[t].size(); k++) {
                            upd(b[t][k], -1);
                        }
                    }
                }

               int l = 0;
               ll Xn = 0;
               for(int k = 0; k < b[1].size(); k++) {
                    while(l < b[0].size() && h[b[0][l]] < h[b[1][k]]) ++l;
                    Xn += (int)b[0].size() - l;
               }
               c1 += Xn;
               c2 += (ll)((int)b[1].size() * (int)b[0].size()) - Xn;
            }
            c1 += C; c2 += C;
            if(c1 <= c2) cn += c1, s += '2';
            else s += "21", cn += c2;
        }
        if(cn < CN) CN = cn, S = s;

    }
    return {CN, S};
}
bool cmp(int a, int b) {
    return (h[a] < h[b]);
}
main(){

    cin >> n;
    if(n == 0) {
        cout << 0;
        return 0;
    }
    vector<int> x;
    for(int i = 0; i + 1 <= (1 << n); i++) {
        cin >> h[i];
        P[i] = i;
    }
    sort(P, P + (1 << n), cmp);
    _ p = solve(n);
    for(int i = 0; i < (1 << (n - 1)); i++) {
        swap(h[i], h[i + (1 << (n - 1))]);
    }
    sort(P , P + (1 << n), cmp);
    _ p2 = solve(n);
    cout << min(p2.f, p.f) << endl;
    if(p2.f < p.f) cout << 1 << p2.s;
    else cout << p.s;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'void upd(int, int)':
cheerleaders.cpp:13:9: warning: statement has no effect [-Wunused-value]
   13 |     for(x; x >= 1; x -= x & (-x)) t[x] += val;
      |         ^
cheerleaders.cpp: In function 'int get(int)':
cheerleaders.cpp:18:9: warning: statement has no effect [-Wunused-value]
   18 |     for(x; x <= (1 << n); x += x & (-x)) ans += t[x];
      |         ^
cheerleaders.cpp: In function 'std::pair<long long int, std::__cxx11::basic_string<char> > solve(int)':
cheerleaders.cpp:32:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                 for(int k = 0; k < v[j].size(); k++) {
      |                                ~~^~~~~~~~~~~~~
cheerleaders.cpp:38:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                         for(int k = 0; k < b[t].size(); k++) {
      |                                        ~~^~~~~~~~~~~~~
cheerleaders.cpp:42:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                         for(int k = 0; k < b[t].size(); k++) {
      |                                        ~~^~~~~~~~~~~~~
cheerleaders.cpp:50:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                for(int k = 0; k < b[1].size(); k++) {
      |                               ~~^~~~~~~~~~~~~
cheerleaders.cpp:51:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                     while(l < b[0].size() && h[b[0][l]] < h[b[1][k]]) ++l;
      |                           ~~^~~~~~~~~~~~~
cheerleaders.cpp: At global scope:
cheerleaders.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28