ccbeginner

UVa Q10549

Mar 3rd, 2020
112
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10549
  2. /******************************************************************************
  3.  
  4.                               Online C++ Compiler.
  5.                Code, Compile, Run and Debug C++ program online.
  6. Write your code in this editor and press "Run" button to compile and execute it.
  7.  
  8. *******************************************************************************/
  9.  
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13. struct wawa{
  14.     int h,d,w;
  15. }arr[200];
  16.  
  17. bool cmp(wawa a, wawa b){
  18.     return (a.h == b.h)? a.d > b.d : a.h > b.h;
  19. }
  20.  
  21. int n;
  22. vector<int> v[2];
  23. bool vis[200][200][100];
  24.  
  25. bool dfs(int idx){
  26.     if(!v[0].empty() && !v[1].empty() && (vis[v[1].back()][v[0].back()][v[1].size()] || vis[v[0].back()][v[1].back()][v[0].size()]))return 0;
  27.     if(idx == 2 * n)return 1;
  28.     for(int i = 0; i < 2; ++i){
  29.         if(v[i].size() == n)continue;
  30.         if(v[i].empty() || (arr[v[i].back()].h-2*arr[v[i].back()].w >= arr[idx].h && arr[v[i].back()].d-2*arr[v[i].back()].w >= arr[idx].d)){
  31.             v[i].emplace_back(idx);
  32.             if(dfs(idx+1))return 1;
  33.             vis[v[0].back()][v[1].back()][v[0].size()] = true;
  34.             v[i].pop_back();
  35.         }
  36.     }
  37.     return 0;
  38. }
  39.  
  40. int main(){
  41.     int start = 1;
  42.     while(cin >> n){
  43.         if(n == 0)break;
  44.         if(start)start = 0;
  45.         else cout << '\n';
  46.         memset(vis, 0, sizeof(vis));
  47.         v[0].clear();
  48.         v[1].clear();
  49.         for(int i = 0; i < 2*n; ++i)cin >> arr[i].h >> arr[i].d >> arr[i].w;
  50.         sort(arr, arr + 2 *n, cmp);
  51.         dfs(0);
  52.         for(int i = 0; i < v[0].size(); ++i)cout << arr[v[0][i]].h << ' ' << arr[v[0][i]].d << ' ' << arr[v[0][i]].w << '\n';
  53.         cout << '-' << '\n';
  54.         for(int i = 0; i < v[1].size(); ++i)cout << arr[v[1][i]].h << ' ' << arr[v[1][i]].d << ' ' << arr[v[1][i]].w << '\n';
  55.     }
  56.     return 0;
  57. }
RAW Paste Data