제출 #1061412

#제출 시각아이디문제언어결과실행 시간메모리
1061412stdfloat순열 (APIO22_perm)C++17
91.33 / 100
2 ms352 KiB
#include <bits/stdc++.h> #include "perm.h" // #include "grader.cpp" 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(); if (x == 1) { int ln = 0, b = 0; while (x != k) { ln++; if (m[x]) x <<= 1; else b++; x++; } int a = b - 1; x = 1; vector<int> v = {b++}; while (x != k) { if (m[x]) { x <<= 1; v.push_back(b++); } else { v.push_back(a--); } x++; } return v; } 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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...