제출 #1200089

#제출 시각아이디문제언어결과실행 시간메모리
1200089browntoadPermutation (APIO22_perm)C++20
85.23 / 100
3 ms584 KiB
#include "perm.h" #include <bits/stdc++.h> using namespace std; #define ll long long // #define int ll #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define REP1(i, n) FOR(i, 1, n+1) #define RREP(i, n) for (int i = (n)-1; i >= 0; i--) #define pii pair<int, int> #define f first #define s second #define pb push_back #define ALL(x) (x).begin(), (x).end() #define SZ(x) (int)((x).size()) namespace{ const ll maxn = 1e5+5; const ll mod = 1e9+7; const ll inf = (1ll<<60); } pair<int, vector<int>> make_bin(long long k, int cur){ // other method: make with binary k--; vector<int> ret; if (k == 0) return {cur, ret}; for (int i = 6; i >= 1; i--){ ll tmp = (1<<i)-1; while (k >= tmp){ k -= tmp; vector<int> poo; REP(j, i) poo.pb(cur++); RREP(j, SZ(poo)) ret.pb(poo[j]); } } reverse(ALL(ret)); return {cur, ret}; } pair<int, vector<int>> make_bao(long long k, int cur){ k--; vector<int> ret; if (k == 0) return {cur, ret}; REP(i, k) ret.pb(cur++); reverse(ALL(ret)); return {cur, ret}; } std::vector<int> construct_permutation(long long k){ k--; // imma make it a bunch of sums vector<int> ret; // initially all reversed int cur = 0; for (int b = 55; b >= 0; b -= 5){ ll tmp = (1ll<<b); int cnt = 0; while(tmp * (cnt+1) - 1 <= k){ cnt++; } if (cnt == 0) continue; cnt--; k -= tmp * (cnt+1) - 1; // goal is to have other side of product = cnt+1 vector<int> ra, rb; REP(i, b){ ra.pb(cur++); } pair<int, vector<int>> c1 = make_bin(cnt+1, cur), c2 = make_bao(cnt+1, cur); if (c1.f < c2.f){ rb = c1.s; cur = c1.f; } else{ rb = c2.s; cur = c2.f; } RREP(i, SZ(rb)) ret.pb(rb[i]); RREP(i, SZ(ra)) ret.pb(ra[i]); } reverse(ALL(ret)); return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...