Submission #482059

#	Time	Username	Problem	Language	Result	Execution time	Memory
482059		Redhood	Cheerleaders (info1cup20_cheerleaders)	C++14	26 / 100	2079 ms	7756 KiB

cheerleaders

#include<bits/stdc++.h>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second

using namespace __gnu_pbds;
using namespace std;
using namespace __gnu_cxx;
using namespace std;

typedef long long ll;

map < vector < int > , int > was;
map < vector < int > , vector < int > > pr;
int cnt;


queue < vector < int > > Q;
int F;

void out(vector < int > p){
  int b;
    b = F;
    for(auto i : p){
        for(int f = b-1; f >= 0; --f){
            if((1 << f) & i)
                cout<<1;
            else cout<<0;
        }
        cout << '\n';
    }
}
const int N = (1 << 10) + 100;
int fen[N];
void modify(int x , int pl){
    for(; x < N; x += x & -x)
        fen[x] += pl;
}
int get(int p){
    int ans = 0;
    for(; p > 0; p -= p & -p)
        ans += fen[p];
    return ans;
}
ll inv(vector < int > &p){
    ll ans = 0;
    for(int i : p){
        ans += get(N - 1 - i);
        modify(N - 1 - i , +1);
    }
    for(int i : p)
        modify( N - 1 - i , -1);
    return ans;
}
vector < int > h;


ll ans = 1e18;
vector < int > answer;
void rek(vector < int > pp){
    /// first op
    was[pp] = 0;
    Q.push(pp);
    while(!Q.empty()){
        vector < int > p = Q.front();

        vector < int > P = p;
        for(int x = 0; x < sz(P); ++x)
            P[x] = h[P[x]];
        ll now = inv(P);
        if(now < ans){
//            cout << "LOL\n";
            ans = now;
            answer = pr[p];
//            for(auto u : pr[p])
//                cout << u << ' ';
//            cout << endl;
        }


        Q.pop();
        int st = was[p];
        cnt++;
        vector < int > s;
        for(int i= 0; i < sz(p); ++i){
            if((i+1) & 1)
                s.pb(p[i]);
        }
        for(int i= 0; i < sz(p); ++i){
            if(i & 1)
                s.pb(p[i]);
        }


        if(was.find(s) == was.end()){
            was[s] = st + 1;
            pr[s] = pr[p];
            pr[s].pb(2);
            Q.push(s);
        }
        s.clear();
        for(int i = sz(p)/2; i < sz(p); ++i){
            s.pb(p[i]);
        }
        for(int i = 0; i < sz(p)/2;++i){
            s.pb(p[i]);
        }
        if(was.find(s) == was.end()){
            was[s] = st + 1;
            pr[s] = pr[p];
            pr[s].pb(1);
            Q.push(s);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    F = n;
    h.resize((1 << n));

    for(auto &i : h)
        cin >> i;



    vector < int > p((1 << n));
    iota(all(p), 0);
    rek(p);

    cout << ans << endl;
    for(auto u : answer)
        cout<<u;


    return 0;
}

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