Submission #428487

#	Time	Username	Problem	Language	Result	Execution time	Memory
428487		jamezzz	Cheerleaders (info1cup20_cheerleaders)	C++17	0 / 100	2084 ms	2484 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];
vector<int> v,ans,t[2];

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(int i){
	memset(ft,0,sizeof ft);
	ll res=0;
	for(int x:t[i]){
		res+=qry(x);
		up(1,1);up(x+1,-1);
	}
	return res;
}

int main(){
	sf("%d",&n);n=(1<<n);
	for(int i=0;i<n;++i){
		sf("%d",&x);v.pb(++x); 
	}
	swap(v,t[0]);
	ll pv=inv(0);
	swap(v,t[0]);
	while(true){
		//pf("%lld\n",pv);
		t[0].clear();t[1].clear();
		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]);
		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 x:t[0])pf("%d ",x);pf("\n");
		//for(int x:t[1])pf("%d ",x);pf("\n");
		ll a=inv(0),b=inv(1);
		if(a>pv&&b>pv)break;
		if(a<b){
			ans.pb(1);
			swap(v,t[0]);
			pv=a;
		}
		else{
			ans.pb(2);
			swap(v,t[1]);
			pv=b;
		}
	}
	pf("%lld\n",pv);
	for(int x:ans)pf("%d",x);
	pf("\n");
}

Compilation message (stderr)

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

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