제출 #707536

#제출 시각아이디문제언어결과실행 시간메모리
707536600Mihnea순열 (APIO22_perm)C++17
91.33 / 100
12 ms344 KiB
#include "perm.h" #include <cmath> #include <functional> #include <fstream> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <cassert> #include <bitset> #include <sstream> #include <chrono> #include <cstring> #include <numeric> using namespace std; typedef long long ll; int get_nr_bits(ll x) { if (x == 0) { return 0; } assert(x >= 1); return get_nr_bits(x / 2) + x % 2; } vector<int> normalize(vector<int> v) { map<int, int> mp; for (auto& x : v) { mp[x] = 0; } int y = 0; for (auto& it : mp) { it.second = y++; } for (auto& x : v) { x = mp[x]; } return v; } vector<int> construct_permutation(ll total) { if (total == 1) { return {}; } vector<int> perm; while (1) { int sz = (int)perm.size(); int next_sz = 1 + sz; if ((1LL << next_sz) <= total) { perm.push_back(sz); } else { break; } } int curval = (int)1e9 + 7; ll cur = (1LL << (int)perm.size()); while (cur < total) { for (int i = (int)perm.size() - 1; i >= -1; i--) { int small = 0; for (int j = 0; j <= i; j++) { small += (perm[j] <= 100); } if (small != i + 1) { continue; } if (cur + (1LL << small) <= total) { cur += (1LL << small); vector<int> nperm; for (int j = 0; j <= i; j++) { nperm.push_back(perm[j]); } nperm.push_back(curval++); for (int j = i + 1; j < (int)perm.size(); j++) { nperm.push_back(perm[j]); } perm = nperm; break; } } } assert(cur == total); perm = normalize(perm); return perm; for (auto& p : perm) { cout << p << " "; } exit(0); for (int k = 1; 1; k++) { ll rem = total + (k - 1); int nr_bits = get_nr_bits(rem); if (k < nr_bits) { continue; } if (rem & (1LL << 0)) { continue; } // split rem into nr_bits bits assert(k >= nr_bits); vector<int> dims; for (int i = 1; (1LL << i) <= rem; i++) { if (rem & (1LL << i)) { dims.push_back(i); } } int need_extra = k - nr_bits; for (int i = 0; i < (int)dims.size(); i++) { while (dims[i] >= 2 && need_extra > 0) { dims.push_back(dims[i] - 1); dims[i]--; need_extra--; } } assert(need_extra == 0); int sumtotal = 0; for (auto& d : dims) { sumtotal += d; } vector<int> sol; for (auto& x : dims) { sumtotal -= x; for (int i = 0; i < x; i++) { sol.push_back(sumtotal + i); } } //cout << " : "; //for (auto& x : sol) //{ // cout << x << " "; //} //cout << "\n"; return sol; } return {}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...