Submission #3390402

---

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];
int n; 
set<int> S;

int dfs(int u, int fixed=-1)
{
	if(visited[u]) return ranking[u];
	visited[u]=1;
	int mx = -1;
	for(int i=0;i<n;i++)
	{
		if(u&(1<<i))
		{
			int res = dfs(u^(1<<i));
			mx=max(mx,res);
		}
	}
	if(fixed!=-1)
	{
		if(fixed<=mx){cout<<"NO\n"; exit(0);}
		if(S.find(fixed)==S.end()){cout<<"NO\n"; exit(0);}
		S.erase(fixed); ranking[u]=fixed;
		return fixed;
	}
	auto it = S.upper_bound(mx);
	if(it==S.end()){cout<<"NO\n"; exit(0);}
	ranking[u]=(*it); S.erase(ranking[u]);
	return ranking[u];
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen("full-tournament.in","r",stdin);
	//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));
		S.insert(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());
	for(int i=0;i<vec.size();i++)
	{
		int needpos = vec[i].fi; int id = vec[i].se;
		if(ranking[id]!=-1){cout<<"NO\n"; return 0;}
		/*
		for(int i=0;i<(1<<n);i++)
		{
			cerr<<ranking[i]+1<<' ';
		}
		cerr<<"NEEDPOS "<<needpos<<" ID "<<id<<'\n';
		*/
		dfs(id,needpos);
	}
	/*
	for(int i=0;i<(1<<n);i++)
	{
		cerr<<ranking[i]+1<<' ';
	}
	cerr<<'\n';
	*/
	/*
	bool ss=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)^(ranking[u]<ranking[v])){cerr<<"FAIL "<<u<<' '<<v<<' '<<ranking[u]<<' '<<ranking[v]<<'\n'; return 0; ss=0; break;}
		}
		if(!ss) break;
	}
	*/
	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