fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace __gnu_pbds;
  4. using namespace std;
  5.  
  6. #define ff              first
  7. #define ss              second
  8. #define int             long long
  9. #define pb              push_back
  10. #define mp              make_pair
  11. #define pii             pair<int,int>
  12. #define vi              vector<int>
  13. #define mii             map<int,int>
  14. #define pqb             priority_queue<int>
  15. #define pqs             priority_queue<int,vi,greater<int> >
  16. #define setbits(x)      __builtin_popcountll(x)
  17. #define zrobits(x)      __builtin_ctzll(x)
  18. #define mod             1000000007
  19. #define inf             1e18
  20. #define ps(x,y)         fixed<<setprecision(y)<<x
  21. #define mk(arr,n,type)  type *arr=new type[n];
  22. #define w(x)            int x; cin>>x; while(x--)
  23. mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
  24.  
  25. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  26.  
  27.  
  28. void c_p_c()
  29. {
  30. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  31. #ifndef ONLINE_JUDGE
  32. 	freopen("/home/krishna/Documents/competitive/input.txt", "r", stdin);
  33. 	freopen("/home/krishna/Documents/competitive/output.txt", "w", stdout);
  34. #endif
  35. }
  36.  
  37. int32_t main()
  38. {
  39. 	c_p_c();
  40. 	w(t)
  41. 	{
  42. 		int n;
  43. 		cin>>n;
  44. 		mk(arr,n,int)
  45. 		for(int i=0;i<n;i++)
  46. 		{
  47. 			cin>>arr[i];
  48. 		}
  49. 		int primes[11]={2,3,5,7,11,13,17,19,23,29,31};
  50. 		mk(ans,n,int);
  51. 		//memset(ans,-1ll,sizeof(ans));
  52. 		for(int i=0;i<n;i++)
  53. 		{
  54. 			ans[i]=-1;
  55. 		}
  56. 		int currentCol=1;
  57. 		for(auto prime:primes)
  58. 			{
  59. 				bool gotColor=false;
  60. 				for(int i=0;i<n;i++)
  61. 				{
  62. 					if(ans[i]==-1)
  63. 					{
  64. 						if(arr[i]%prime==0)
  65. 						{
  66. 							ans[i]=currentCol;
  67. 							gotColor=true;
  68. 						}
  69. 					}
  70. 				}
  71. 				if(gotColor)
  72. 					currentCol++;
  73. 			}
  74. 			cout<<currentCol-1<<"\n";
  75. 			for(int i=0;i<n;i++)
  76. 			{
  77. 				cout<<ans[i]<<" ";
  78. 			}
  79. 			cout<<endl;
  80. 	}
  81. 	return 0;
  82. }
Success #stdin #stdout 0s 4272KB
comments (?)
stdin
copy 
3
3
6 10 15
2
4 9
23
437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961
stdout
copy 
2
1 1 2 
2
1 2 
10
8 2 3 1 2 7 1 2 2 3 7 3 4 4 5 5 6 6 7 7 8 9 10
https://ideone.com/Kw4oKf
language:
C++14 (gcc 8.3)
created:
6 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!