Submission #573521

#	Time	Username	Problem	Language	Result	Execution time	Memory
573521		neonaht	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	340 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int SZ=207;
int fen[SZ];

void update(int x,int val) {
	while(x<SZ) {
		fen[x]+=val;
		x+=(x&-x);
	}
	return ;
}

int query(int x) {
	int sum(0);
	while(x) {
		sum+=fen[x];
		x-=(x&-x);
	}
	return sum;
}

std::vector<int> construct_permutation(long long k)
{
	for(int i=0;i<SZ;i++) fen[i]=0;
	if(k==2) return {0};
	--k;
	vector <int> res,seq;
	ll cnt(0),v(2),z=k;
	int maxi(0);
	while(z) {
		++cnt;
		z>>=1LL;
	}
	--cnt;
	for(int i=1;i<=cnt;i++) update(i,1);
	seq.emplace_back(1);
	ll Bit=(1LL<<(cnt-1));
	bool chx=true;
	while(Bit) {
		if(chx) {
			if(k&Bit) {
				if(v>cnt) seq.insert(seq.begin(),query(v-1)+1);
				else seq.insert(seq.begin(),query(v));
				update(v,1);
				chx=false;
			}
			++v;
			Bit>>=1LL;
		}else {
			if(k&Bit && k&(Bit>>1LL)) {
				if(v+1>cnt) seq.insert(seq.begin()+2,query(v)+1);
				else seq.insert(seq.begin()+2,query(v+1));
				update(v+1,1);
			}else if(k&Bit) {
				if(v>cnt) seq.insert(seq.begin(),query(v-1)+1);
				else seq.insert(seq.begin(),query(v));
				update(v,1);
			}else if(k&(Bit>>1LL)) {
				if(v+1>cnt) seq.insert(seq.begin(),query(v)+1);
				else seq.insert(seq.begin(),query(v+1));
				update(v+1,1);
			}
			v+=2;
			Bit>>=2LL;
		}
	}
	for(auto x:seq) maxi=max(maxi,x);
	for(int i=2;i<=cnt;i++) maxi=max(maxi,query(i));
	res.emplace_back(maxi);
	for(auto x:seq) res.emplace_back(x-1);
	for(int i=2;i<=cnt;i++) res.emplace_back(query(i)-1);
	return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90