# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
914853 | 2024-01-22T18:31:27 Z | starchan | 순열 (APIO22_perm) | C++17 | 199 ms | 1356 KB |
#include<bits/stdc++.h> #include "perm.h" using namespace std; #define int long long #define double long double #define in pair<int, int> #define f first #define s second #define pb push_back #define pob pop_back #define INF (int)1e17 #define MX (int)3e5+5 #define SSX (int)6 #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) bool no_pre = true; vector<pair<double, pair<in, vector<int>>>> bruter; vector<pair<double, pair<in, vector<int>>>> brute; bool valid(const vector<int> &t) { vector<int> a(SSX+1, 0), b(SSX+1, 0); for(int i = 0; i < t.size(); i++) { if(t[i] > 0) a[t[i]]++; else b[-t[i]]++; } for(int i = 1; i < SSX; i++) { if((a[i] >= 2) || (b[i] >= 2)) return false; if(i && (a[i] < a[i+1])) return false; if(i && (b[i] < b[i+1])) return false; } return true; } int inc_sub(const vector<int> &t) { if(t.empty()) return 1; int n = t.size(); int dp[n]; int ans = 2; dp[0] = 1; for(int i = 1; i < n; i++) { dp[i] = 1; for(int j = 0; j < i; j++) { if(t[j] < t[i]) dp[i]+=dp[j]; } ans+=dp[i]; } return ans; } in linear(const vector<int> &v) { vector<int> b; for(int k: v) { if(k > 0) b.pb(k); } int X = inc_sub(b); int Y = inc_sub(v); return {X, Y-X}; } void assimilate(int u) { vector<int> v; int k = 1; for(int i = 1; i <= u; i++) { k*=(2*u); v.pb(-i); v.pb(i); } vector<int> ch; for(int msk = 0; msk < k; msk++) { ch.clear(); int cop = msk; for(int i = 1; i <= u; i++) { ch.pb(v[cop%(2*u)]); cop/=(2*u); } if(valid(ch)) { auto ab = linear(ch); double U = u; double a = ab.f; double b = log(a); U = U/b; bruter.pb({U, {ab, ch}}); } } } void pre() { assert(no_pre); no_pre = false; for(int i = 1; i <= SSX; i++) assimilate(i); sort(bruter.begin(), bruter.end()); brute.pb(bruter[0]); in prev = bruter[0].s.f; for(int k = 1; k < bruter.size(); k++) { if(bruter[k].s.f == prev) continue; brute.pb(bruter[k]); prev = bruter[k].s.f; } return; } void bruh(vector<int> &x, int v) { if(v == 1) return; for(int i = 0; i < brute.size(); i++) { auto [a, b] = brute[i].s.f; if(v <= b) continue; if(v > b) { if((v-b)%a) continue; v-=b; v/=a; bruh(x, v); x.pb(i); return; } } return; } vector<signed> construct_permutation(int K) { if(no_pre) pre(); vector<int> d; bruh(d, K); int lb = 1; int ub = 0; vector<signed> v; for(int i = 0; i < d.size(); i++) { int t1 = 0; int t2 = 0; for(int k: brute[d[i]].s.s) { if(k > 0) { t1 = max(t1, k); v.pb((signed)(ub+k)); } else { t2 = min(t2, k); v.pb((signed)(lb+k)); } } lb+=t2; ub+=t1; } signed KK = 200; for(auto r: v) KK = min(KK, r); for(int i = 0; i < v.size(); i++) v[i]-=(KK); return v; } /*signed main() { srand(time(0)); for(int i = 1e18; i <= 1e18+100; i++) { return 0; }*/
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 173 ms | 1028 KB | Output is correct |
2 | Correct | 173 ms | 1228 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 173 ms | 1028 KB | Output is correct |
2 | Correct | 173 ms | 1228 KB | Output is correct |
3 | Correct | 192 ms | 1316 KB | Output is correct |
4 | Correct | 176 ms | 1260 KB | Output is correct |
5 | Correct | 181 ms | 1224 KB | Output is correct |
6 | Correct | 191 ms | 1356 KB | Output is correct |
7 | Correct | 178 ms | 1212 KB | Output is correct |
8 | Correct | 175 ms | 1228 KB | Output is correct |
9 | Correct | 176 ms | 1228 KB | Output is correct |
10 | Correct | 199 ms | 1088 KB | Output is correct |
11 | Correct | 177 ms | 1300 KB | Output is correct |
12 | Correct | 184 ms | 1072 KB | Output is correct |
13 | Correct | 179 ms | 1172 KB | Output is correct |