Submission #577337

#	Time	Username	Problem	Language	Result	Execution time	Memory
577337		handlename	Permutation (APIO22_perm)	C++17	91.33 / 100	3 ms	388 KiB

perm

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int MOD=1e9+7;
int n;
long long num[63];
long long ft[201];
void upd(int x,long long v){
	while (x<=n){
		ft[x]+=v;
		if (ft[x]>1e18) ft[x]=1e18+1;
		x+=x&-x;
	}
}
long long qry(int x){
	long long res=0;
	while (x>0){
		res+=ft[x];
		if (res>1e18) res=1e18+1;
		x-=x&-x;
	}
	return res;
}
int lol(vector<int> arr){
	n=arr.size();
	long long res=1;
	for (int i=1;i<=n;i++) ft[i]=0;
	for (auto i:arr){
		long long cur=qry(i+1)+1;
		upd(i+1,cur);
		res+=cur;
	}
	//cout<<"try ";
	//for (auto i:arr) cout<<i<<' ';
	//cout<<res<<'\n';
	return res;
}
vector<int> construct_permutation(long long k){
	vector<int> temp;
	if (k==1) return temp;
	temp.pb(0);
	if (k==2) return temp;
	vector<int> lol=construct_permutation(k/2);
	lol.pb(lol.size());
	if (k%2==1){
		temp.clear();
		temp.pb(lol.size());
		for (auto i:lol) temp.pb(i);
		return temp;
	}
	return lol;
}

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