Submission #1201777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201777		adiyer	Permutation (APIO22_perm)	C++20	100 / 100	9 ms	328 KiB

perm

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e9;

vector < int > construct_permutation(ll k){
    ll bit = 0, was = 0;
    for(ll i = 0; i < 60; i++)
        if(k >= (1ll << i))
            bit = i + 1;
    vector < double > ans;
    map < double, int > val;
    while(bit > 0){
        bit -= 2;
        if(bit == -1){
            ans.push_back(inf);
            if(k & 1) ans.push_back(-inf);
            continue;
        }
        ll v = (k >> bit) & 3;
        if(ans.empty()){
            if(v == 2) ans = {0};
            else ans = {1, 0}, was = 1;
            continue;
        }
        if(v == 0) ans.push_back(inf), ans.push_back(inf + 1);
        else if(v == 1) ans.push_back(inf), ans.push_back(inf + 1), ans.push_back(-inf), was = 1;
        else if(v == 2) ans.push_back(inf), ans.push_back(-inf), ans.push_back(inf + 1), was = 1;
        else if(!was) ans.push_back(inf), ans.push_back(-inf), ans.push_back(inf + 1), ans.push_back(-inf - 1), was = 1;
        else ans.push_back(inf), ans.push_back(inf + 1), ans.push_back(1.5); 
        vector < double > c = ans;
        sort(c.begin(), c.end());
        for(ll i = 0; i < c.size(); i++) val[c[i]] = i;
        for(ll i = 0; i < ans.size(); i++) ans[i] = val[ans[i]];
    }    
    vector < double > c = ans;
    sort(c.begin(), c.end());
    for(ll i = 0; i < c.size(); i++) val[c[i]] = i;
    for(ll i = 0; i < ans.size(); i++) ans[i] = val[ans[i]];
    vector < int > res;
    for(auto &i : ans) res.push_back(i);
    return res;
}

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