Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using pdi = pair<double, int>;
- using ld = long double;
- using vd = vector<double>;
- const ld EPS = 1e-10;
- int n;
- // given a proposed point x, is the point x/rem_wt in the permutahedron?
- bool feasible(const vd& x, ld rem_wt) {
- vector<pdi> srtd(n);
- for (int i = 0; i < n; ++i) {
- if (x[i] < -EPS) return false; // nonnegativity must hold
- srtd[i] = pdi(x[i], i);
- }
- sort(srtd.begin(), srtd.end());
- // each prefix sum of smallest i items better be at least 1 + ... + i
- ld tot_x = 0.0;
- for (int i = 0; i < n; ++i) {
- tot_x += srtd[i].first;
- if (tot_x < rem_wt*(i+1)*(i+2)*0.5 - EPS) return false;
- }
- // but in total we need n*(n+1)/2 value
- if (tot_x > rem_wt*n*(n+1)*(0.5) + EPS) return false;
- return true;
- }
- int main() {
- cin >> n;
- vd x(n);
- for (auto& v : x) cin >> v;
- if (!feasible(x, 1.0)) {
- cout << -1 << endl;
- return 0;
- }
- vector<vector<int>> perms;
- vd wt;
- ld rem_wt = 1.0;
- vector<pdi> srtd(n);
- vector<int> p(n);
- vd tmp(n);
- // Idea
- // Consider the permutation corresponding to the sorted order of values
- // (eg if the values are x[] = 3 2 2.9 2.1 then the permutation is p[] = 4 1 3 2)
- // We want to write x[] = a*p[] + (1-a)*t[] where 0 <= a <= 1
- // where t is also in the permutahedron (scaled by rem_wt), so binary search for the largest a
- // such that t[] = (x[] - a*p[])/(1-a)
- // (for future iterations, replace 1 above with rem_wt)
- // # iterations of the while loop is <= n because each iteration will make some permutahedron
- // constraint go tight and will remain tight as the algorithm progresses
- while (rem_wt > EPS) {
- for (int i = 0; i < n; ++i) srtd[i] = pdi(x[i], i);
- sort(srtd.begin(), srtd.end());
- for (int i = 0; i < n; ++i) p[srtd[i].second] = i;
- ld lo = 0.0, hi = rem_wt;
- while (lo + EPS*0.5 < hi) {
- ld mid = (lo+hi)*0.5;
- for (int i = 0; i < n; ++i) tmp[i] = x[i] - mid*(p[i]+1);
- if (feasible(tmp, rem_wt - mid)) lo = mid;
- else hi = mid;
- }
- for (int i = 0; i < n; ++i) x[i] -= lo*(p[i]+1);
- perms.push_back(p);
- wt.push_back(lo);
- rem_wt -= lo;
- }
- cout.setf(ios::fixed);
- cout.precision(10);
- cout << perms.size() << endl;
- for (int i = 0; i < perms.size(); ++i) {
- cout << wt[i];
- for (int id : perms[i]) cout << ' ' << id+1;
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement