Guest User

Untitled

a guest
Apr 23rd, 2020
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.35 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define forn(i,n) for(i=0;i<n;++i)
  8. #define for1(i,n) for(i=1;i<=n;++i)
  9. #define eb emplace_back
  10. #define all(x) (x).begin(),(x).end()
  11. #define fill(x,b) memset((x),b,sizeof((x)))
  12. #define fill2D(x,r,c,b) memset((x),b, sizeof(x[0][0]) * r * c)
  13. #define whatIs(a) cout<<#a<<" is : "<<a<<endl
  14.  
  15. typedef long long ll;
  16. typedef vector<int> vi;
  17. typedef vector<ll> vll;
  18. typedef vector<vi> vvi;
  19. typedef vector<vll> vvll;
  20. typedef vector<string> vs;
  21. typedef vector<vs> vvs;
  22.  
  23. const int mod = 1e9 + 7;
  24. clock_t t1,t2;
  25.  
  26. ll binPow(ll a, ll b){ll x = 1, y = a;while (b){if (b & 1)x = (x * y) % mod;y = (y*y) % mod;b >>= 1;}return x % mod;}
  27.  
  28. ll inverserEuler(int n){return binPow(n, mod-2);}
  29.  
  30. ll C(int k, int n){vll f(n+1,1);for(int i = 2;i<=n;i++)f[i] = (f[i-1]*i)%mod;return (f[n] * ((inverserEuler(f[k]) * inverserEuler(f[n-k]))%mod)%mod)%mod;}
  31.  
  32. /* Extend Euclid: ax + by = c;
  33. ll x, y;
  34.  
  35. void extendEuclid(ll a, ll b){if(b == 0){x = 1;y = 0;return;}extendEuclid(b,a%b);ll x1 = y, y1 = x - (a/b) * y;x = x1;y = y1;}
  36. // nghiem : x + (b/d)*k, y - (a/d) * k;
  37. */
  38. /*--------------------------------------------------------------------------------------------------*/
  39.  
  40. const int manx = 2e5 + 5;
  41.  
  42. void trunghieu()
  43. {
  44.     int n, m, d;
  45.     cin>>n>>m>>d;
  46.     int i,j, ans = 0;
  47.     vector<pair<int,int>> a(n);
  48.     forn(i,n)
  49.     {
  50.         cin>>a[i].first;
  51.         a[i].second = i;
  52.     }
  53.     sort(begin(a), end(a));
  54.     int cnt = 1;
  55.     unordered_map<int,int> visited,day;
  56.     forn(i,n){
  57.         if(!visited[a[i].second]){
  58.             int begin = a[i].first;
  59.             day[a[i].second] = cnt;
  60.             while(begin <= m){
  61.                 int id = lower_bound(a.begin() + i, a.end(), make_pair(begin + d + 1, numeric_limits<int>::min())) - a.begin();
  62.                 if(id >= a.size())
  63.                     break;
  64.                 while(visited[a[id].second] && id < a.size())
  65.                     id++;
  66.                 if(id >= a.size())
  67.                     break;
  68.                 day[a[id].second] = cnt;
  69.                 visited[a[id].second] = 1;
  70.                 begin = a[id].first;
  71.             }
  72.             cnt++;
  73.         }
  74.     }
  75.     cout<<cnt-1<<endl;
  76.     forn(i,n)
  77.         cout<<day[i]<<" ";
  78. }
  79.  
  80. int main()
  81. {
  82.     ios::sync_with_stdio(false);
  83.     cin.tie();
  84.     #ifndef ONLINE_JUDGE
  85.         freopen("input.txt","r",stdin);
  86.         //freopen("output.txt","w",stdout);
  87.     #endif
  88.     trunghieu();
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment