fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <map>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. template <typename It>
  9.  
  10. void PrintRange(It range_begin, It range_end) {
  11. 	for (auto it = range_begin; it != range_end; ++it) {
  12. 		cout << *it << " "s;
  13. 	}
  14. 	cout << endl;
  15. }
  16.  
  17.  
  18.  
  19. int main() {
  20. 	int n;
  21. 	int d;
  22. 	cin>>n>>d;
  23. 	vector<pair<int,int>> v(3*n);
  24. 	vector<int> stud(n);
  25. 	for(int i=0;i<n;i++){
  26. 		int x;
  27. 		cin>>x;
  28. 		v[3*i]={2*x-d,-1};
  29. 		v[3*i+1]={2*x+d,1};
  30. 		v[3*i+2]={2*x,0};
  31. 		stud[i]=2*x;
  32. 	}
  33. 	sort(v.begin(),v.end());
  34. //	PrintRange(v.begin(),v.end());
  35. 	int cur=0;
  36. 	int minbil=0;
  37. 	for(int i=0;i<3*n;i++){
  38. //		cout<<i<<", "s<<v[i].first<<", "s<<v[i].second<<", "s<<cur<<endl;
  39. 		if(v[i].second==-1){
  40. 			cur++;
  41. 		} else if(v[i].second==1){
  42. 			cur--;
  43. 		} else if(v[i].second==0){
  44.  
  45. 		}
  46. 			minbil=max(minbil,cur);
  47. 	}
  48.  
  49.  
  50. 	map<int,vector<int>> ma;
  51. 	cur=0;
  52. 	for(int i=0;i<3*n;i++){
  53. //		cout<<i<<", "s<<v[i].first<<", "s<<v[i].second<<endl;	
  54. 		if(v[i].second==0){
  55. //			cout<<cur%minbil<<endl;
  56. 			ma[v[i].first].push_back(cur%minbil);
  57. //			PrintRange(ma[v[i].first].begin(),ma[v[i].first].end());
  58. 			cur++;
  59. 		}
  60. 	}
  61.  
  62. 	cout<<minbil<<endl;
  63.  
  64.  
  65. 	for(int i=0;i<n;i++){
  66. 		cout<<ma[stud[i]].back()+1<<" "s;
  67. //		PrintRange(ma[stud[i]].begin(),ma[stud[i]].end());
  68. 		ma[stud[i]].pop_back();
  69. 	}
  70.  
  71.  
  72. 	return 0;
  73. }
Success #stdin #stdout 0.01s 5660KB
comments (?)
stdin
copy 
10 3
12 13 17 0 5 14 6 7 16 4
stdout
copy 
4
2 3 2 1 3 4 4 1 1 2
https://ideone.com/HRGk84
language:
C++14 (gcc 8.3)
created:
2 years 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!