Submission #476644

#	Time	Username	Problem	Language	Result	Execution time	Memory
476644		leaked	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	1232 ms	5020 KiB

cheerleaders

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define m_p make_pair
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)x.size()
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<long long,long long> pll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
auto rng=bind(uniform_int_distribution<int>(1,20),mt19937(time(0)));
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
const int N=17;
const ll inf=1e18;
const int M=1e9+7;
int n;
template <class T> using oset=tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void move1(vec<int> &p){
    for(auto &z : p){
        z=z^(pw(n-1));
    }
}
void move2(vec<int> &p){
    for(auto &z : p){
        if(z&1)
            z>>=1,z|=pw(n-1);
        else
            z>>=1;
    }
}
vec<int> getxr(int x){
    vec<int>need(n+1,0);
    for(int i=0;i<n;i++){
        if(pw(i)&x){
            need[n-i-1]=1;
        }
    }
    vec<int>vc;
    for(int i=n-1;i>=0;i--){
//        if(need[i]) vc.pb(1);
        vc.pb(2);
        if(need[i]) vc.pb(1);
//        if(need[i]) vc.pb(2);
    }
    vec<int>lel={0};
    for(auto &z : vc){
        if(z==1) move1(lel);
        else move2(lel);
    }
//    debug()<<imie(lel)imie(x)imie(vc);
    assert(lel[0]==x);
    return vc;
}
ll cnt[N][2];
vec<int> p;
int a[1<<N];
vec<int> rec(int i,vec<int> x){
    if(i==-1) return x;
    vec<int> g1,g2;
    for(auto &t : x){
        if(p[t]&(1<<i)) g2.pb(t);
        else g1.pb(t);
    }
    g1=rec(i-1,g1);g2=rec(i-1,g2);
    int uk=0;
    for(auto &t : g2){
        while(uk!=sz(g1) && a[t]>a[g1[uk]]) uk++;
//        debug()<<imie(i)imie(uk)imie(sz(g2)-uk);
        cnt[i][1]+=uk;
        cnt[i][0]+=sz(g2)-uk;
    }
    x.clear();
    merge(all(g1),all(g2),back_inserter(x),[&](int t,int b){return a[t]<a[b];});
//    for(int i=1;i<sz(x);i++)
//        assert(a[x[i-1]]<a[x[i]]);
//    debug()<<imie(i)imie(x);
    return x;
}
signed main(){
    fast_ioi;
    cin>>n;

    for(int i=0;i<(1<<n);i++) cin>>a[i];
//    return 0;

//    vec<int>a(1<<n);
//    for(auto &z : a) cin>>z;
    ll total=inf;
    vec<int>rops;
    p.assign(1<<n,0);
    iota(all(p),0);
    vec<int>ob=p;
    vec<int>vt;
    for(int f=0;f<=n;f++){
        for(int i=0;i<n;i++){
            cnt[i][0]=cnt[i][1]=0;
        }
//        vec<vec<ll>>st(n,vec<ll>(2,0));
//        for(int i=0;i<(1<<n);i++){
//            for(int j=0;j<i;j++){
//                int w=p[i]^p[j];
//                w=31-__builtin_clz(w);
//                if(p[i]<p[j]){
//                    if(a[i]>a[j]) st[w][0]++;
//                    else st[w][1]++;
//                }
//                else{
//                    if(a[i]>a[j]) st[w][1]++;
//                    else st[w][0]++;
//                }
//            }
//        }
        vec<int>hah=rec(n-1,ob);
        int w=0;ll ans=0;
        for(int i=0;i<n;i++){
//            debug()<<imie(how[i][0])imie(how[i][1]);
//            debug()<<im
//            assert(st[i][0]==cnt[i][0]);
//            assert(st[i][1]==cnt[i][1]);
            if(cnt[i][0]<cnt[i][1]) ans+=cnt[i][0];
            else ans+=cnt[i][1],w^=(1<<i);
        }
//        vec<int>hah=rec(0,ob);
        vec<int>ops=getxr(w);
        for(auto &q : vt) ops.insert(ops.begin(),q);
        if(umin(total,ans)){
            rops=ops;
        }
        move2(p);vt.pb(2);

//        cout<<endl;
    }
    cout<<total<<endl;
    for(auto &z : rops)
        cout<<z;
    return 0;
}
/*

*/

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