Guest User

Untitled

a guest
Jun 30th, 2014
1,072
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define in freopen("input.txt","r",stdin);
  3. #define out freopen("output.txt","w",stdout);
  4. using namespace std;
  5. const int MX = 1000001;
  6. const int MI = 100001;
  7. const int MT = 10001;
  8. int dp[101][10001];
  9. int used[101];
  10. int main(){
  11.     //in out
  12.     //ios::sync_with_stdio(false);
  13.     //double sttm = clock();
  14.     int n, m = 0, a[101];
  15.     scanf("%d", &n);
  16.     for(int i=1; i<=n; ++i)
  17.         scanf("%d", &a[i]),
  18.             m += a[i], used[i] ++;
  19.     sort(a + 1, a + n + 1);
  20.     reverse(a + 1, a + n + 1);
  21.     if(m % 2 == 1 || n % 2 == 1){
  22.         puts("No solution");
  23.         return 0;
  24.     }
  25.     m = m / 2;
  26.     for(int i=1; i<=n; ++i){
  27.         for(int j=1; j<=m; ++j){
  28.             dp[i][j] = dp[i-1][j];
  29.             if(j - a[i] >= 0){
  30.                 dp[i][j] = max(dp[i][j], dp[i-1][j-a[i]]+a[i]);
  31.             }
  32.         }
  33.     }
  34.     if(dp[n][m] != m){
  35.         puts("No solution");
  36.         return 0;
  37.     }
  38.     vector <int> ans1, ans2;
  39.     int x = n, y = m;
  40.     while(x){
  41.         if(dp[x][y] != dp[x-1][y]){
  42.             ans1 . push_back(x);
  43.             used[x] --;
  44.             y -= a[x]; x --;
  45.         }
  46.         else x --;
  47.     }
  48.     for(int i=1; i<=n; ++i){
  49.         while(used[i] > 0){
  50.             ans2 . push_back(i);
  51.             used[i] --;
  52.         }
  53.     }
  54.     if(ans1.size() != ans2.size()){
  55.         puts("No solution");
  56.         return 0;
  57.     }
  58.     else{
  59.         sort(ans1.begin(), ans1.end());
  60.         sort(ans2.begin(), ans2.end());
  61.         for(int i=0; i<ans1.size(); ++i)
  62.             printf("%d ", ans1[i]);
  63.         puts("");
  64.         for(int i=0; i<ans2.size(); ++i)
  65.             printf("%d ", ans2[i]);
  66.         puts("");
  67.     }
  68.     //cout << (clock() - sttm) / CLOCKS_PER_SEC << endl;
  69.     return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment