Submission #3390308

---

Source Code Expand

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

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int a[(1<<18)+10];

vi get_rank(vi V)
{
	int n = V.size();
	if(n==1) return {V[0]};
	vi L,R;
	for(int i=0;i<n;i+=2)
	{
		L.pb(min(V[i],V[i+1]));
		R.pb(max(V[i],V[i+1]));
	}
	vi rankL = get_rank(L); vi rankR = get_rank(R);
	for(int v:rankR) rankL.pb(v); 
	return rankL;
}

void brute()
{
	vi perm;
	int n = 3;
	for(int i=0;i<(1<<n);i++) perm.pb(i);
	do
	{
		cerr<<"INITIAL :\n";
		for(int v:perm)
		{
			cerr<<v<<' ';
		}
		cerr<<'\n';
		vi rankings = get_rank(perm);
		cerr<<"RANKINGS :\n";
		for(int v:rankings)
		{
			cerr<<v<<' ';
		}
		cerr<<'\n';
		bool pos=1;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<(1<<n);j++)
			{
				int u = j; int v = j^(1<<i);
				if((u<v)^(rankings[u]<rankings[v])){pos=0; break;}
			}
			if(!pos) break;
		}
		if(!pos)
		{
			for(int v:perm) cout<<v<<' ';
			return ;
		}
	}while(next_permutation(perm.begin(),perm.end()));
}

bool visited[(1<<18)+12];
int ranking[(1<<18)+12];
vi V;
int n; 

void dfs(int u)
{
	if(visited[u]) return ;
	V.pb(u); visited[u]=1;
	for(int i=0;i<n;i++)
	{
		if(u&(1<<i))
		{
			dfs(u^(1<<i));
		}
	}
}

bool used[(1<<18)+12];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	//brute(); return 0;
	cin>>n;
	for(int i=0;i<(1<<n);i++)
	{
		cin>>a[i]; a[i]--;
	}
	if(a[0]>=1){cout<<"NO\n"; return 0;}
	memset(ranking,-1,sizeof(ranking));
	vector<ii> vec;
	for(int i=0;i<(1<<n);i++)
	{
		if(a[i]>=0) vec.pb(mp(a[i],i));
	}
	vec.pb(mp(0,0)); vec.pb(mp((1<<n)-1,(1<<n)-1));
	sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end());
	int pos=0;
	for(int i=0;i<vec.size();i++)
	{
		int needpos = vec[i].fi; int id = vec[i].se;
		if(used[needpos]){cout<<"NO\n"; return 0;}
		/*
		for(int i=0;i<(1<<n);i++)
		{
			cerr<<ranking[i]+1<<' ';
		}
		cerr<<"NEEDPOS "<<needpos<<" ID "<<id<<'\n';
		*/
		V.clear();
		dfs(id);
		sort(V.begin(),V.end());
		//cerr<<V.size()<<' '<<pos<<'\n';
		for(int i=0;i+1<V.size();i++)
		{
			while(used[pos]) pos++;
			if(pos>=needpos){cout<<"NO\n"; return 0;}
			used[pos]=1; ranking[V[i]] = pos++; 
		}
		ranking[id] = needpos; used[needpos]=1;
	}
	/*
	for(int i=0;i<(1<<n);i++)
	{
		cerr<<ranking[i]+1<<' ';
	}
	cerr<<'\n';
	*/
	vi res;
	res.pb(0);
	for(int i=0;i<n;i++)
	{
		vi nw;
		for(int v:res)
		{
			nw.pb(v); nw.pb(v+(1<<i));
		}
		res=nw;
	}
	for(int i=0;i<(1<<n);i++) res[i]=ranking[res[i]];
	cout<<"YES\n";
	for(int i=0;i<(1<<n);i++)
	{
		cout<<res[i]+1;
		if(i+1<(1<<n)) cout<<' ';
	}
	cout<<'\n';
}

Submission Info

Judge Result