Advertisement
Kaidul

10249

May 15th, 2013
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.43 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cctype>
  4. #include <cmath>
  5. #include <complex>
  6. #include <cstdio>
  7. #include <cstdlib>
  8. #include <cstring>
  9. #include <ctime>
  10. #include <deque>
  11. #include <fstream>
  12. #include <iostream>
  13. #include <list>
  14. #include <map>
  15. #include <memory>
  16. #include <queue>
  17. #include <set>
  18. #include <sstream>
  19. #include <stack>
  20. #include <string>
  21. #include <utility>
  22. #include <vector>
  23. #include <iomanip>
  24. using namespace std;
  25. /*** typedef ***/
  26. #define MEMSET_INF 127
  27. #define MEMSET_HALF_INF 63
  28. #define stream istringstream
  29. #define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
  30. #define repl(i,n) for(__typeof(n) i=1; i<=(n); i++)
  31. #define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
  32. #define INF (1<<30)
  33. #define PI acos(-1.0)
  34. #define pb push_back
  35. #define ppb pop_back
  36. #define all(x) x.begin(),x.end()
  37. #define mem(x,y) memset(x,y,sizeof(x))
  38. #define memsp(x) mem(x,MEMSET_INF)
  39. #define memdp(x) mem(x,-1)
  40. #define memca(x) mem(x,0)
  41. #define eps 1e-9
  42. #define pii pair<int,int>
  43. #define pmp make_pair
  44. #define ft first
  45. #define sd second
  46. #define vi vector<int>
  47. #define vpii vector<pii>
  48. #define si set<int>
  49. #define msi map<string , int >
  50. #define mis map<int , string >
  51. typedef long long i64;
  52. typedef unsigned long long ui64;
  53. /** function **/
  54. #define SDi(x) sf("%d",&x)
  55. #define SDl(x) sf("%lld",&x)
  56. #define SDs(x) sf("%s",x)
  57. #define SD2(x,y) sf("%d%d",&x,&y)
  58. #define SD3(x,y,z) sf("%d%d%d",&x,&y,&z)
  59. #define pf printf
  60. #define print(x) pf("%d ", x)
  61. #define println(x) pf("%d\n", x)
  62. #define sf scanf
  63. #define READ(f) freopen(f, "r", stdin)
  64. #define WRITE(f) freopen(f, "w", stdout)
  65.  
  66. /** Main Code **/
  67.  
  68. #define NTeam 70
  69. #define NTable 50
  70. #define Max 200
  71.  
  72. struct team {
  73.     int id, member_no;
  74.     team() {}; // empty constructor to satisfy bokachoda compiler
  75.     team(int a, int b) {id = a; member_no = b;}
  76.     bool operator < (const team& a) const {
  77.         return member_no < a.member_no;
  78.     }
  79. };
  80.  
  81. struct table {
  82.     int id, capacity;
  83.     table() {};
  84.     table(int a, int b) {id = a; capacity = b;}
  85.     bool operator < (const table& a) const {
  86.         return capacity > a.capacity;
  87.     }
  88. }t[NTable + 10];
  89.  
  90. priority_queue <team> q;
  91. map < int, map <int ,int> > track;
  92. int m, n;
  93.  
  94. bool isPossible() {
  95.     int table_remain = n, member;
  96.     team top;
  97.     table t_obj;
  98.     while(!q.empty()) {
  99.         top = q.top(), q.pop();
  100.         member = top.member_no;
  101.         if(member > table_remain) return false;
  102.         rep(i, member) {
  103.             t_obj = t[i];
  104.             t_obj.capacity -= 1;
  105.             track[top.id][i] = t_obj.id;
  106.             t[i] = t_obj; // restore
  107.             if(!t_obj.capacity) table_remain -= 1;
  108.         }
  109.     }
  110.     return true;
  111. }
  112.  
  113. int main() {
  114.     #ifndef ONLINE_JUDGE
  115.         READ("input.txt");
  116.     #endif
  117.     int team_member, capacity, temp[NTeam + 10];
  118.     bool result;
  119.     while(SD2(m, n) && n && m) {
  120.         q = priority_queue <team> ();
  121.         rep(i, m) SDi(team_member), temp[i] = team_member, q.push(team(i, team_member));
  122.         rep(i, n) SDi(capacity), t[i] = table(i, capacity);
  123.         sort(t, t + n);
  124.  
  125.         result = isPossible();
  126.         println(result);
  127.         if(result) {
  128.             rep(i, m) {
  129.                 int arr[Max];
  130.                 rep(j, temp[i]) arr[j] = track[i][j] + 1;
  131.                 sort(arr, arr + temp[i]);
  132.                 rep(j, temp[i]) pf("%d ", arr[j]);
  133.                 pf("\n");
  134.             }
  135.         }
  136.     }
  137.     return 0;
  138. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement