hpnq

Untitled

Jan 5th, 2023
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2.  
  3. //speed coding
  4.  
  5. #define mp make_pair
  6. #define cve(a) for (auto i : a) {cout << i << " ";  } cout << "\n";
  7. #define f first
  8. #define s second
  9. #define loop(i, x, n) for (int i = x; i < n; i++)
  10. #define joop(x, n) for (ll j = x; j < n; j++)
  11. #define err cout << "ERROR" << endl;
  12. #define all(x) x.begin(), x.end()
  13. #define pb push_back
  14. #define sz(x) x.size()
  15.  
  16. // types
  17. #define pii pair<int, int>
  18. #define pll pair<ll, ll>
  19. #define vvi vector<vector<int>>
  20. #define vvll vector<vector<ll>>
  21. typedef long long ll;
  22.  
  23. // types of data
  24. #define inf 1000000000
  25. #define infll 1000000000000000000
  26. #define mod 998244343
  27.  
  28. //#define DEBUG 1
  29. using namespace std;
  30.  
  31. char dp[111][111][10011] = {0};
  32. ll a[110];
  33. void solve() {
  34.     int  n;
  35.     cin >> n;
  36.     int  m = 0;
  37.     loop(i, 0, n) {
  38.         cin >> a[i];
  39.         m += a[i];
  40.     }
  41.     if (m % 2 != 0 || n % 2 != 0) {
  42.         cout << -1;
  43.         return;
  44.     }
  45.     loop(i, 0, n + 1) {
  46.         dp[i][0][0] = 1;
  47.     }
  48.     loop(pref, 1, n + 1) {
  49.         loop(cnt, 1, pref + 1) {
  50.             loop(sum, 1, m + 1) {
  51.                 dp[pref][cnt][sum] = dp[pref - 1][cnt][sum] || dp[pref-1][cnt-1][sum - a[pref - 1]];
  52.             }
  53.         }
  54.     }
  55.     int sum = m / 2;
  56.     int cnt = n / 2;
  57.     int pref = n;
  58.     if (dp[pref][cnt][sum] == 0) {
  59.         cout << -1;
  60.         return;
  61.     }
  62.     set<int> st; // max 100
  63.     while (sum != 0) {
  64.         if (dp[pref - 1][cnt - 1][sum - a[pref - 1]] && sum-a[pref - 1] >= 0) {
  65.             st.insert(pref);
  66.             cout << pref << " ";
  67.             sum -= a[pref - 1];
  68.             cnt--;
  69.         }
  70.         pref--;
  71.     }
  72.     cout << endl;
  73.  
  74.     loop(i, 1, n + 1) {
  75.         if (st.count(i) == 0) {
  76.             cout << i << " ";
  77.         }
  78.     }
  79. }
  80.  
  81. int main() {
  82.     ios::sync_with_stdio(0);
  83.     cin.tie(0);
  84. #ifdef DEBUG
  85.     freopen("text.txt", "r", stdin);
  86. #else
  87. #endif
  88.     solve();
  89.     return 0;
  90. }
  91.  
Advertisement
Add Comment
Please, Sign In to add comment