yeputons

Untitled

Jul 11th, 2012
138
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <cassert>
  6. #include <algorithm>
  7. #include <string>
  8. #include <vector>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13.  
  14. using namespace std;
  15.  
  16. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(x) ((int)(x).size())
  20.  
  21. typedef long long ll;
  22. typedef vector<ll> vll;
  23. typedef vector<int> vi;
  24. typedef vector<vi> vvi;
  25. typedef vector<bool> vb;
  26. typedef vector<vb> vvb;
  27. typedef pair<int, int> pii;
  28.  
  29. const int MAXN = 1e5 + 1e3;
  30. const int MAXM = 1e6 + 1e3;
  31.  
  32. int n, d, m;
  33. int firs[MAXN];
  34. int nes[MAXM];
  35.  
  36. int ids[MAXN];
  37. int nes2[MAXM];
  38.  
  39. bool check(int maxw, bool write = false) {
  40.   if (write) {
  41.     memset(firs, -1, sizeof firs);
  42.   }
  43.  
  44.   int ptr = 0, csz = 0;
  45.   for (int cst = 0; cst < n; cst++)
  46.   for (int i = ids[cst]; i >= 0; i = nes2[i]) {
  47.     while (ptr < cst) { ptr++; csz = 0; }
  48.     if (csz >= maxw) { ptr++; csz = 0; }
  49.  
  50.     if (ptr >= n || ptr > cst + d) return false;
  51.     csz++;
  52.     if (write) {
  53.       nes[i] = firs[ptr];
  54.       firs[ptr] = i;
  55.     }
  56.   }
  57.   return true;
  58. }
  59.  
  60. int main() {
  61.   #ifdef DEBUG
  62.   freopen("std.in", "r", stdin);
  63.   freopen("std.out", "w", stdout);
  64.   #endif
  65.  
  66.   while (scanf("%d%d%d", &n, &d, &m) >= 1) {
  67.     memset(ids, -1, sizeof ids);
  68.     for (int i = 0; i < m; i++) {
  69.       int x;
  70.       scanf("%d", &x), x--;
  71.       nes2[i] = ids[x];
  72.       ids[x] = i;
  73.     }
  74.  
  75.     int L = 0, R = m;
  76.     assert(check(R));
  77.     while (L + 1 < R) {
  78.       int M = (L + R) / 2;
  79.       if (check(M)) R = M;
  80.       else L = M;
  81.     }
  82.     printf("%d\n", R);
  83.  
  84.     check(R, true);
  85.     for (int i = 0; i < n; i++) {
  86.       for (int i2 = firs[i]; i2 >= 0; i2 = nes[i2])
  87.         printf("%d ", i2 + 1);
  88.       printf("0\n");
  89.     }
  90.  
  91.     #ifndef DEBUG
  92.     break;
  93.     #endif
  94.   }
  95.   return 0;
  96. }
RAW Paste Data