1654F - Minimal String Xoration - CodeForces Solution

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cctype>

#include<vector>

#include<bitset>

#include<random>

#include<ctime>

#include<queue>

#include<cmath>

#include<list>

#include<map>

#include<set>

#define pb push_back

#define mp make_pair

#define pii pair<int,int>

#define pll pair<long long,long long>

#define FF fflush(stdout)

#define inf 0x3f3f3f3f

#define endl "\n"

#define fi first

#define se second

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

char buf[1<<20],*p1,*p2;

//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)

inline int read()

{

	int s=0,f=1;

	char x=getchar();

	while(!isdigit(x))f=(x=='-'?-1:1),x=getchar();

	while(isdigit(x))s=s*10+x-'0',x=getchar();

	return s*f;

}

mt19937 rd(58);

#define reaD read

int n;

char s[1<<19];

int rk[1<<19],sa[1<<19],ssa[1<<19];

int c[1<<19];

int M;

void qsort()

{

	for(int i=0;i<(1<<n);i++)c[rk[i]]++;

	for(int i=2;i<=M;i++)c[i]+=c[i-1];

	for(int i=(1<<n);i>=1;i--)sa[c[rk[ssa[i]]]--]=ssa[i];

	for(int i=1;i<=M;i++)c[i]=0;

}

void build()

{

	for(int i=0,w=1;i<n;i++,w<<=1)

	{

		for(int j=1;j<=(1<<n);j++)

		ssa[j]=sa[j]^w;

		qsort();swap(ssa,rk);

		rk[sa[1]]=1;int p=1;

		for(int j=2;j<=(1<<n);j++)

		rk[sa[j]]=(ssa[sa[j]]==ssa[sa[j-1]]&&ssa[sa[j]^w]==ssa[sa[j-1]^w]?p:++p);

		M=p;

		if(M==(1<<n))break;

	}

}

int main()

{

	n=reaD();

	scanf("%s",s);

	for(int i=0;i<(1<<n);i++)

	rk[i]=s[i]-'a'+1,ssa[i+1]=i;

	M=26;

	qsort();

	build();

//	for(int i=1;i<=(1<<n);i++)cout<<sa[i]<<" ";

	for(int i=0;i<(1<<n);i++)

	putchar(s[i^sa[1]]);

	return 0;

}