Submission #577335

#	Time	Username	Problem	Language	Result	Execution time	Memory
577335		handlename	Permutation (APIO22_perm)	C++17	10 / 100	1099 ms	340 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){
	num[0]=1;
	for (int i=1;i<63;i++){
		num[i]=num[i-1]*2;
	}
	vector<int> ans;
	for (int whack=0;whack<1;whack++){
		vector<int> arr;
		for (int i=0;i<whack;i++) arr.pb(i);
		do{
			vector<int> res;
			for (auto i:arr) res.pb(i);
			if (k-lol(res)<0) continue;
			while (lol(res)<k){
				vector<int> temp=res;
				int id[temp.size()];
				for (int i=0;i<(int) temp.size();i++){
					id[temp[i]]=i;
					temp[i]++;
				}
				temp.pb(0);
				for (int i=1;i<=(int) res.size();i++){
					temp[id[i-1]]--;
					temp.pop_back();
					temp.pb(i);
					if (lol(temp)>k){
						temp[id[i-1]]++;
						temp.back()--;
						break;
					}
				}
				res=temp;
			}
			if (ans.empty() || ans.size()>res.size()){
				ans=res;
			}
		} while (next_permutation(arr.begin(),arr.end()));
	}
	return ans;
}

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