제출 #897025

#제출 시각아이디문제언어결과실행 시간메모리
897025d4xn순열 (APIO22_perm)C++17
71.22 / 100
768 ms1680 KiB
#include "perm.h" #include <bits/stdc++.h> using namespace std; #define ll long long const int N = 5e3+3, M = 3e2+2, X = 5e2+2, Y = 50; const ll L = 62; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<int> construct_permutation(ll k) { vector<int> p; if (!k) return p; ll K = k; k--; int r = N; //vector<int> p2; for (int j = L; j > 0; j--) { //cerr << k << " " << j << " " << (1ll << j) << " " << (1ll << j) - 1ll << endl; if (k >= (1ll << j) - 1ll) { k -= (1ll << j) - 1ll; for (int l = 1; l <= j; l++) { /*p2*/p.push_back(r-j+l); } //cerr << j << endl; r -= j; j = L+1; } } /*if (p.empty() || p2.size() < p.size()) swap(p, p2); }*/ for (int i = 1; i <= M; i++) { // cojo i subsequences // he de sumar k+i-1 ll nwK = K + i - 1; int cnt[L+1]; for (int j = L; j >= 0; j--) { cnt[j] = (((nwK >> j) & 1) ? 1 : 0); } int c = __builtin_popcountl(nwK); while (c < i) { bool b = 0; for (int j = L; j > 0; j--) { if (cnt[j]) { cnt[j-1] += 2; cnt[j]--; c++; b = 1; break; } } if (!b) break; } if (c != i) continue; //cerr << "cojo " << i << endl; r = N; vector<int> p2; for (int j = L; j >= 0; j--) { while (cnt[j]--) { for (int l = 1; l <= j; l++) { p2.push_back(r-j+l); //cerr << r-j+l << endl; } r -= j; } } if (p.empty() || p2.size() < p.size()) swap(p, p2); } for (int tt = 0; tt < Y; tt++) { k = K-1; r = N; vector<int> p2; while (k) { int j = rng() % L + 1; if (k >= (1ll << j) - 1ll) { k -= (1ll << j) - 1ll; for (int l = 1; l <= j; l++) { p2.push_back(r-j+l); } //cerr << j << endl; r -= j; } } if (p.empty() || p2.size() < p.size()) swap(p, p2); } for (int tt = 0; tt < X; tt++) { k = K-1; r = N; vector<int> p2; for (int j = L; j > 0; j--) { //cerr << k << " " << j << " " << (1ll << j) << " " << (1ll << j) - 1ll << endl; if (k >= (1ll << j) - 1ll && rng() % 2) { k -= (1ll << j) - 1ll; for (int l = 1; l <= j; l++) { p2.push_back(r-j+l); } //cerr << j << endl; r -= j; j = L+1; } if (k && j == 1) j = L+1; } if (p.empty() || p2.size() < p.size()) swap(p, p2); } int sz = p.size(); for (int i = 0; i < sz; i++) { p[i] -= N-sz+1; } return p; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...