oj.uz

Submission #577337

# Submission time Handle Problem Language Result Execution time Memory
577337 2022-06-14T14:47:50 Z handlename Permutation (APIO22_perm) C++17
91.3333 / 100
 3 ms 388 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
81.333333333 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Partially correct 2 ms 340 KB Partially correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Partially correct 2 ms 340 KB Partially correct
9 Correct 1 ms 340 KB Output is correct
10 Partially correct 3 ms 340 KB Partially correct
11 Partially correct 2 ms 340 KB Partially correct
12 Partially correct 2 ms 340 KB Partially correct
13 Partially correct 2 ms 388 KB Partially correct