Submission #572593

#	Time	Username	Problem	Language	Result	Execution time	Memory
572593		arthur_nascimento	Permutation (APIO22_perm)	C++17	0 / 100	1 ms	212 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
using namespace std;

std::vector<int> construct_permutation(long long k)
{
	
    k++;
    ll aux = k, sz = 0;
    
    while(aux)
        aux /= 2, sz++;
        
        
    vector<pii> ans;
    
    for(int i=0;i<sz-1;i++)
        ans.pb({2*i,i+1});
        
    vector<int> dec;
    dec.pb(1);
    
    int x = 1, y = 0, skip = 0;
    
    for(int i=sz-2;i>=0;i--, x += 2, y--){
        
        if((k & (1ll << i)) == 0) continue;
        
        if(skip){
            skip = 0;
            ans.pb({x,dec[dec.size()-2]+1});
            continue;
        }
        
        
        if(dec.size() == 1 || i == 0 || (k & (1ll << (i-1))) == 0){
            
            ans.pb({x,y});
            dec.pb(y);
            
            
        }
        
        else {
    
            skip = 1;
            
        }
        
        
        
    }
    
    sort(ans.begin(), ans.end());
    
    int c = 0;
    for(auto &p : ans)  p.first = c++;
    
    c = 0;
    sort(ans.begin(), ans.end(), [](pii i,pii j){
        if(i.second == j.second) return i.first > j.first;
        return i.second < j.second;
    });
    
    for(auto &p : ans)  p.second = c++;
    
    sort(ans.begin(), ans.end());

	vector<int> r;
	for(auto p : ans)
		r.pb(p.second);

    return r;

}

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