oj.uz

Submission #596984

# Submission time Handle Problem Language Result Execution time Memory
596984 2022-07-15T11:00:02 Z cfalas Permutation (APIO22_perm) C++17
91.3333 / 100
 2 ms 340 KB 
#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

vi tr(long long k, int off){
	vi a;
	int cnt=62;
	long long qq = (1LL<<off);
	if(k<qq) return vi(5000, 0);
	k-=qq;
	while(k>0 && cnt>off){
		while(k>=(1LL<<cnt)-qq){
			k-=((1LL<<cnt)-qq);
			a.push_back(cnt-off);
		}
		cnt--;
	}
	//cout<<k<<" left"<<endl;
	vi b;
	int p=off-1;
	for(auto v : a){
		for(int i=p+v;i>p;i--){
			b.push_back(i);
		}
		p = p+v;
	}
	for(int i=off-1;i>=0;i--) b.push_back(i);
	while(k) b.push_back(++p), k--;
	reverse(b.begin(), b.end());

	return b;
}

vector<int> construct_permutation(long long k)
{
	vi ans;
	int cnt=61;
	int aa=0;
	vi ins;
	while(cnt>=0){
		if(k&(1LL<<cnt)){
			ins.push_back(cnt);
			if(ans.size()==0){
				for(int i=0;i<cnt;i++) ans.push_back(i);
				aa = cnt;
			}
			else{
				ans.insert(ans.begin()+cnt, aa++);
			}
		}
		cnt--;
	}
	/*
	for(int i=0;i<20;i++){
		vi b = tr(k, i);
		if(b.size()<ans.size() || ans.size()==0) ans = b;
	}*/
	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
81.333333333 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 304 KB Partially correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Partially correct 2 ms 340 KB Partially correct
9 Correct 1 ms 300 KB Output is correct
10 Partially correct 2 ms 340 KB Partially correct
11 Partially correct 2 ms 304 KB Partially correct
12 Partially correct 1 ms 296 KB Partially correct
13 Partially correct 2 ms 340 KB Partially correct