Submission #428829

#	Time	Username	Problem	Language	Result	Execution time	Memory
428829		jamezzz	Cheerleaders (info1cup20_cheerleaders)	C++17	26 / 100	2117 ms	380396 KiB

cheerleaders

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define pb emplace_back
typedef long long ll;

#define maxn 131077

int n,x,ft[maxn];
ll best;
vector<int> v,cur,ans;
set<vector<int>> vis;

void up(int x,int nv){
	while(x<=n)ft[x]+=nv,x+=x&-x;
}
int qry(int x){
	int res=0;
	while(x)res+=ft[x],x-=x&-x;
	return res;
}
ll inv(){
	memset(ft,0,sizeof ft);
	ll res=0;
	for(int x:v){
		res+=qry(x);
		up(1,1);up(x+1,-1);
	}
	return res;
}

void dfs(){
	if(vis.count(v))return;
	vis.insert(v);
	ll tmp=inv();
	if(tmp<best){
		best=tmp;
		ans=cur;
	}
	vector<int> t[2];
	for(int i=n/2;i<n;++i)t[0].pb(v[i]);
	for(int i=0;i<n/2;++i)t[0].pb(v[i]);
	for(int i=0;i<n;i+=2)t[1].pb(v[i]);
	for(int i=1;i<n;i+=2)t[1].pb(v[i]);
	cur.pb(1);
	swap(v,t[0]);
	dfs();
	cur.pop_back();
	swap(v,t[0]);
	swap(v,t[1]);
	cur.pb(2);
	dfs();
	cur.pop_back();
	swap(v,t[1]);
}

int main(){
	sf("%d",&n);n=(1<<n);
	for(int i=0;i<n;++i){
		sf("%d",&x);v.pb(++x); 
	}
	best=inv();
	dfs();
	pf("%lld\n",best);
	for(int x:ans)pf("%d",x);
	pf("\n");
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:60:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  sf("%d",&n);n=(1<<n);
      |    ^
cheerleaders.cpp:62:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   sf("%d",&x);v.pb(++x);
      |     ^

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