fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 100005;
  5. const int MAXM = 1000005;
  6.  
  7. int n, d, m;
  8. vector<int> a[MAXN];
  9. int bd[MAXM];
  10.  
  11. bool kt(int cnt)
  12. {
  13.     queue<int> q;
  14.  
  15.     for (int i = 1; i <= n; i++)
  16.     {
  17.         for (int id : a[i])  q.push(bd[id]);
  18.  
  19.         int sl = 0;
  20.         while (!q.empty() && sl < cnt)
  21.         {
  22.             if (i > q.front() + d) return 0;
  23.             q.pop();
  24.             sl++;
  25.         }
  26.  
  27.         if (!q.empty() && i > q.front() + d) return 0;
  28.     }
  29.     return q.empty();
  30. }
  31.  
  32. int main()
  33. {
  34.     ios::sync_with_stdio(0);
  35.     cin.tie(0);
  36.     cout.tie(0);
  37.     cin>>n>>d>>m;
  38.     for (int i = 1; i <= m; i++)
  39.     {
  40.         int x;
  41.         cin >> x;
  42.         a[x].push_back(i);
  43.         bd[i] = x;
  44.     }
  45.  
  46.     int l = 1, r = m, ans = m;
  47.     while (l <= r)
  48.     {
  49.         int mid = l + (r - l) / 2;
  50.         if (kt(mid))
  51.         {
  52.             r = mid - 1;
  53.              ans = mid;
  54.         }
  55.         else l = mid + 1;
  56.  
  57.     }
  58.  
  59.     cout << ans << '\n';
  60.  
  61.     queue<int> q;
  62.     for (int i = 1; i <= n; i++)
  63.     {
  64.  
  65.         for (int id : a[i]) q.push(id);
  66.         int sl = 0;
  67.         while (!q.empty() && sl < ans)
  68.         {
  69.             cout << q.front() << " ";
  70.             q.pop();
  71.             sl++;
  72.         }
  73.         cout << 0<<'\n';
  74.     }
  75.  
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 7828KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/JD2Zb1
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!