Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define in freopen("input.txt","r",stdin);
- #define out freopen("output.txt","w",stdout);
- using namespace std;
- const int MX = 1000001;
- const int MI = 100001;
- const int MT = 10001;
- int dp[101][10001];
- int used[101];
- int main(){
- //in out
- //ios::sync_with_stdio(false);
- //double sttm = clock();
- int n, m = 0, a[101];
- scanf("%d", &n);
- for(int i=1; i<=n; ++i)
- scanf("%d", &a[i]),
- m += a[i], used[i] ++;
- sort(a + 1, a + n + 1);
- reverse(a + 1, a + n + 1);
- if(m % 2 == 1 || n % 2 == 1){
- puts("No solution");
- return 0;
- }
- m = m / 2;
- for(int i=1; i<=n; ++i){
- for(int j=1; j<=m; ++j){
- dp[i][j] = dp[i-1][j];
- if(j - a[i] >= 0){
- dp[i][j] = max(dp[i][j], dp[i-1][j-a[i]]+a[i]);
- }
- }
- }
- if(dp[n][m] != m){
- puts("No solution");
- return 0;
- }
- vector <int> ans1, ans2;
- int x = n, y = m;
- while(x){
- if(dp[x][y] != dp[x-1][y]){
- ans1 . push_back(x);
- used[x] --;
- y -= a[x]; x --;
- }
- else x --;
- }
- for(int i=1; i<=n; ++i){
- while(used[i] > 0){
- ans2 . push_back(i);
- used[i] --;
- }
- }
- if(ans1.size() != ans2.size()){
- puts("No solution");
- return 0;
- }
- else{
- sort(ans1.begin(), ans1.end());
- sort(ans2.begin(), ans2.end());
- for(int i=0; i<ans1.size(); ++i)
- printf("%d ", ans1[i]);
- puts("");
- for(int i=0; i<ans2.size(); ++i)
- printf("%d ", ans2[i]);
- puts("");
- }
- //cout << (clock() - sttm) / CLOCKS_PER_SEC << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment