Submission #1202510

#TimeUsernameProblemLanguageResultExecution timeMemory
1202510trashaccountPermutation (APIO22_perm)C++20
Compilation error
0 ms0 KiB
#include "perm.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define isz(a) (int)(a).size() const int NM = 200, MX = 1e9; const ll LIM = 1e18; ll dp[NM+5], bit[NM+5]; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int get_rand(int l, int r){ int tmp = rng()%(r-l+1); if (tmp < 0) tmp += r-l+1; return l + tmp; } void update(int x, ll val){ while (x <= NM){ bit[x] += val; x += x & (-x); } } ll get(int x){ ll res = 0; while (x > 0){ res += bit[x]; x -= x & (-x); } return res; } ll calc(vector <int> &p){ memset(dp, 0, sizeof(dp)); memset(bit, 0, sizeof(bit)); for (int i = 0; i < isz(p); i++){ dp[i] = 1+get(p[i]); update(p[i]+1, dp[i]); } ll res = 1; for (int i = 0; i < isz(p); i++) res += dp[i]; return res; } vector <int> construct_permutation(ll k){ vector <int> p = {0}; while (calc(p) < k){ int l = 1, r = isz(p), res = 0; while (l <= r){ int mid = (l+r)/2; vector <int> p_nxt = p; for (int &x : p_nxt) if (x >= mid) x++; p_nxt.push_back(mid); if (calc(p_nxt) <= k){ res = mid; l = mid+1; } else r = mid-1; } if (res > 0 && rng()%2 != 0) res--; for (int &x : p) if (x >= res) x++; p.push_back(res); } return p; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector <int> p = construct_permutation(LIM); for (int x : p) cout << x << ' '; return 0; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccNzVwrO.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc1sylqW.o:perm.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status