Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- //speed coding
- #define mp make_pair
- #define cve(a) for (auto i : a) {cout << i << " "; } cout << "\n";
- #define f first
- #define s second
- #define loop(i, x, n) for (int i = x; i < n; i++)
- #define joop(x, n) for (ll j = x; j < n; j++)
- #define err cout << "ERROR" << endl;
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define sz(x) x.size()
- // types
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define vvi vector<vector<int>>
- #define vvll vector<vector<ll>>
- typedef long long ll;
- // types of data
- #define inf 1000000000
- #define infll 1000000000000000000
- #define mod 998244343
- //#define DEBUG 1
- using namespace std;
- char dp[111][111][10011] = {0};
- ll a[110];
- void solve() {
- int n;
- cin >> n;
- int m = 0;
- loop(i, 0, n) {
- cin >> a[i];
- m += a[i];
- }
- if (m % 2 != 0 || n % 2 != 0) {
- cout << -1;
- return;
- }
- loop(i, 0, n + 1) {
- dp[i][0][0] = 1;
- }
- loop(pref, 1, n + 1) {
- loop(cnt, 1, pref + 1) {
- loop(sum, 1, m + 1) {
- dp[pref][cnt][sum] = dp[pref - 1][cnt][sum] || dp[pref-1][cnt-1][sum - a[pref - 1]];
- }
- }
- }
- int sum = m / 2;
- int cnt = n / 2;
- int pref = n;
- if (dp[pref][cnt][sum] == 0) {
- cout << -1;
- return;
- }
- set<int> st; // max 100
- while (sum != 0) {
- if (dp[pref - 1][cnt - 1][sum - a[pref - 1]] && sum-a[pref - 1] >= 0) {
- st.insert(pref);
- cout << pref << " ";
- sum -= a[pref - 1];
- cnt--;
- }
- pref--;
- }
- cout << endl;
- loop(i, 1, n + 1) {
- if (st.count(i) == 0) {
- cout << i << " ";
- }
- }
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- #ifdef DEBUG
- freopen("text.txt", "r", stdin);
- #else
- #endif
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment