Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using pdi = pair<double, int>;
  6. using ld = long double;
  7. using vd = vector<double>;
  8. const ld EPS = 1e-10;
  9.  
  10. int n;
  11.  
  12. // given a proposed point x, is the point x/rem_wt in the permutahedron?
  13. bool feasible(const vd& x, ld rem_wt) {
  14.   vector<pdi> srtd(n);
  15.   for (int i = 0; i < n; ++i) {
  16.     if (x[i] < -EPS) return false; // nonnegativity must hold
  17.     srtd[i] = pdi(x[i], i);
  18.   }
  19.   sort(srtd.begin(), srtd.end());
  20.  
  21.   // each prefix sum of smallest i items better be at least 1 + ... + i
  22.   ld tot_x = 0.0;
  23.   for (int i = 0; i < n; ++i) {
  24.     tot_x += srtd[i].first;
  25.     if (tot_x < rem_wt*(i+1)*(i+2)*0.5 - EPS) return false;
  26.   }
  27.  
  28.   // but in total we need n*(n+1)/2 value
  29.   if (tot_x > rem_wt*n*(n+1)*(0.5) + EPS) return false;
  30.   return true;
  31. }
  32.  
  33. int main() {
  34.   cin >> n;
  35.   vd x(n);
  36.   for (auto& v : x) cin >> v;
  37.  
  38.   if (!feasible(x, 1.0)) {
  39.     cout << -1 << endl;
  40.     return 0;
  41.   }
  42.  
  43.   vector<vector<int>> perms;
  44.   vd wt;
  45.   ld rem_wt = 1.0;
  46.  
  47.   vector<pdi> srtd(n);
  48.   vector<int> p(n);
  49.   vd tmp(n);
  50.  
  51.   // Idea
  52.   // Consider the permutation corresponding to the sorted order of values
  53.   // (eg if the values are x[] = 3 2 2.9 2.1 then the permutation is p[] = 4 1 3 2)
  54.   // We want to write x[] = a*p[] + (1-a)*t[] where 0 <= a <= 1
  55.   // where t is also in the permutahedron (scaled by rem_wt), so binary search for the largest a
  56.   // such that t[] = (x[] - a*p[])/(1-a)
  57.   // (for future iterations, replace 1 above with rem_wt)
  58.   // # iterations of the while loop is <= n because each iteration will make some permutahedron
  59.   // constraint go tight and will remain tight as the algorithm progresses
  60.   while (rem_wt > EPS) {
  61.     for (int i = 0; i < n; ++i) srtd[i] = pdi(x[i], i);
  62.     sort(srtd.begin(), srtd.end());
  63.  
  64.     for (int i = 0; i < n; ++i) p[srtd[i].second] = i;
  65.  
  66.     ld lo = 0.0, hi = rem_wt;
  67.     while (lo + EPS*0.5 < hi) {
  68.       ld mid = (lo+hi)*0.5;
  69.       for (int i = 0; i < n; ++i) tmp[i] = x[i] - mid*(p[i]+1);
  70.       if (feasible(tmp, rem_wt - mid)) lo = mid;
  71.       else hi = mid;
  72.     }
  73.  
  74.     for (int i = 0; i < n; ++i) x[i] -= lo*(p[i]+1);
  75.  
  76.     perms.push_back(p);
  77.     wt.push_back(lo);
  78.     rem_wt -= lo;
  79.   }
  80.  
  81.   cout.setf(ios::fixed);
  82.   cout.precision(10);
  83.   cout << perms.size() << endl;
  84.   for (int i = 0; i < perms.size(); ++i) {
  85.     cout << wt[i];
  86.     for (int id : perms[i]) cout << ' ' << id+1;
  87.     cout << endl;
  88.   }
  89.  
  90.   return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement