Submission #476637

#	Time	Username	Problem	Language	Result	Execution time	Memory
476637		leaked	Cheerleaders (info1cup20_cheerleaders)	C++14	35 / 100	2111 ms	281240 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=2001;
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){
        z=(z>>1)|((z&1)*(pw(n-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;
}
signed main(){
    fast_ioi;
    cin>>n;

//    for(int i=0;i<(1<<n);i++) getxr(i);
//    return 0;
    vec<int>a(1<<n);
    for(auto &z : a) cin>>z;
    ll total=inf;
    vec<int>rops;
    vec<int>p(1<<n);
    iota(all(p),0);
    vec<int>vt;
    for(int f=0;f<n;f++){
        vec<vec<oset<int>>>cnt(n,vec<oset<int>>(1<<n,oset<int>()));
        vec<vec<ll>>how(n,vec<ll>(2,0));
        vec<vec<ll>>st(n,vec<ll>(2,0));
        for(int i=0;i<n;i++){
            int full=pw(n)-pw(i);
            for(int j=0;j<(1<<n);j++){
//                debug()<<imie(i)imie(full);
                cnt[i][(full&p[j])].insert(a[j]);
            }
        }
//        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(w==0)debug()<<imie(p[i])imie(p[j])imie(a[i])imie(a[j]);
//                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]++;
//                }
//            }
//        }
        for(int i=0;i<n;i++){
            int full=pw(n)-pw(i);
            for(int j=0;j<(1<<n);j++){
                if((p[j]&pw(i))==0) continue;
                int me=(full&p[j]);
                int yj=cnt[i][me^(1<<i)].order_of_key(a[j]);
                how[i][1]+=yj;
//                debug()<<imie(how[i][0])imie(sz(cnt[me^(1<<i)])-how[i][0]);
                how[i][0]+=sz(cnt[i][me^(1<<i)])-yj;
            }
        }
        int w=0;ll ans=0;
        for(int i=0;i<n;i++){
//            debug()<<imie(how[i][0])imie(how[i][1]);
            if(how[i][0]<how[i][1]) ans+=how[i][0];
            else ans+=how[i][1],w^=(1<<i);
        }
//        debug()<<imie(st)imie(how);
//        assert(st==how);
        vec<int>ops=getxr(w);
//        if(f) {
        for(auto &q : vt) ops.insert(ops.begin(),2);
        if(umin(total,ans)){
            rops=ops;
        }
        move2(p);vt.pb(2);
//        cout<<endl;
    }
    cout<<total<<endl;
    for(auto &z : rops)
        cout<<z;
    return 0;
}
/*

*/

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:152:19: warning: unused variable 'q' [-Wunused-variable]
  152 |         for(auto &q : vt) ops.insert(ops.begin(),2);
      |                   ^

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