Advertisement
K_Y_M_bl_C

Untitled

Sep 17th, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.40 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef vector<int> vi;
  7. typedef pair<int, int> pii;
  8.  
  9. #define ff first
  10. #define ss second
  11. #define y1 y111
  12. #define X first
  13. #define Y second
  14. #define mk make_pair
  15. #define inb push_back
  16. #define all(v) v.begin(), v.end()
  17.  
  18. const int MAXN = (int)1e6 + 9, MAXN1 = (int)2e4 + 7;
  19. const int INFint = (int)1e9 + 7, P = 31;
  20. const ll INFll = (ll)1e18 + 7, MOD = (ll)1e9 + 7;
  21. const double INFfl = 1e18 * 4 + 7;
  22. const double EPS = 1e-7;
  23. const double PI = atan2(0, -1);
  24.  
  25. int solve();
  26.  
  27. int main()
  28. {
  29. #define TASK ""
  30. #ifdef _DEBUG
  31.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  32. #else
  33.     //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  34. #endif
  35.     solve();
  36. }
  37.  
  38. const int STRBUF = (int)1e6 + 7;
  39. char buf[STRBUF];
  40. string get_str()
  41. {
  42.     scanf(" %s", buf);
  43.     return string(buf);
  44. }
  45.  
  46. struct Socket
  47. {
  48.     int x;
  49.     int id, cnt;
  50.     Socket() {};
  51.     Socket(int x, int id) : x(x), id(id), cnt(0) {};
  52.     bool operator< (const Socket &a) const
  53.     {
  54.         if (x == a.x)
  55.         {
  56.             if (cnt == a.cnt)
  57.                 return id < a.id;
  58.             return cnt < a.cnt;
  59.         }
  60.         return x > a.x;
  61.     }
  62. };
  63.  
  64. int solve()
  65. {
  66.     int n, m;
  67.     scanf("%d %d", &n, &m);
  68.     vector<pii> pc(n);
  69.     set<Socket> q;
  70.     for (int i = 0; i < n; ++i)
  71.         scanf("%d", &pc[i].X), pc[i].Y = i;
  72.     for (int i = 0; i < m; ++i)
  73.     {
  74.         int x;
  75.         scanf("%d", &x);
  76.         q.insert(Socket(x, i));
  77.     }
  78.     vector<int> sans(m), pans(n);
  79.     sort(all(pc));
  80.     reverse(all(pc));
  81.     int cntc = 0, cntu = 0;
  82.     for (int l = 0; l < n;)
  83.     {
  84.         if (q.empty())
  85.             break;
  86.         //printf("%d %d %d\n", l, pc[l].X, q.begin()->x);
  87.         while (l < n && pc[l].X > q.begin()->x)
  88.             ++l;
  89.         if (l == n)
  90.             break;
  91.         if (q.begin()->x > pc[l].X)
  92.         {
  93.             Socket nx = *q.begin();
  94.             q.erase(nx);
  95.             nx.cnt++;
  96.             nx.x = (nx.x + 1) / 2;
  97.             q.insert(nx);
  98.         }
  99.         else
  100.         {
  101.             Socket nx = *q.begin();
  102.             q.erase(nx);
  103.             cntu += nx.cnt;
  104.             ++cntc;
  105.             sans[nx.id] = nx.cnt;
  106.             pans[pc[l].Y] = nx.id + 1;
  107.             ++l;
  108.         }
  109.     }
  110.     printf("%d %d\n", cntc, cntu);
  111.     for (int x : sans)
  112.         printf("%d ", x);
  113.     puts("");
  114.     for (int x : pans)
  115.         printf("%d ", x);
  116.     puts("");
  117.     return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement