제출 #1061408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061408		stdfloat	순열 (APIO22_perm)	C++17	91.33 / 100	2 ms	520 KiB

perm

#include <bits/stdc++.h>
#include "perm.h"
using namespace std;

using ll = long long;

vector<int> construct_permutation(ll k) {
    k--;
    ll remk = k;

    // int sm = -1;
    // vector<int> v;
    // while (k) {
    //     int x = __lg(k + 1);

    //     sm += x;
    //     v.push_back(x);
        
    //     k -= (1LL << x) - 1;
    // }

    // if (sm < 90) {
    //     vector<int> ans;
    //     for (int i = 0; i < (int)v.size(); i++) {
    //         for (int j = sm - v[i] + 1; j <= sm; j++) {
    //             ans.push_back(j);
    //         }

    //         sm -= v[i];
    //     }

    //     return ans;
    // }

    k = remk;

    map<ll, bool> m;
    queue<pair<ll, int>> q;
    q.push({k, 0});
    while (!q.empty()) {
        auto [x, tr] = q.front(); q.pop();

        // cout << "x " << x << ' ' << tr << '\n';

        if (x == 1) {
            int ln = 0, b = 0;
            while (x != k) {
                ln++;

                // cout << x << ' ' << m[x] << '\n';

                if (m[x]) x <<= 1;
                else b++;

                x++;
            }

            int a = b - 1;

            // cout << a << ' ' << b << ' ' << ln << ' ' << '\n';

            x = 1;
            vector<int> v = {b++};
            while (x != k) {
                if (m[x]) {
                    x <<= 1;
                    v.push_back(b++);
                }
                else {
                    v.push_back(a--);
                }

                x++;
            }
            
            // for (auto i : v) {
            //     cout << i << ' ';
            // }
            // cout << endl;
            return v;

            exit(false);   
        }

        if (!tr && m.find(x - 1) == m.end()) {
            m[x - 1] = 0;
            q.push({x - 1, 1});
        }
        if ((x & 1) && m.find((x - 1) >> 1) == m.end()) {
            m[(x - 1) >> 1] = 1;
            q.push({(x - 1) >> 1, 0});
        }
    }

    assert(false);
}

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