fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define fi first
  4. #define se second
  5. #define all(a) a.begin(),a.end()
  6.  
  7. using namespace std;
  8.  
  9. mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  10.  
  11. int rnd(int l,int r) 
  12. {
  13.     uniform_int_distribution<int> uid(l,r);
  14.     return uid(mt);
  15. }
  16.  
  17. typedef pair<int, int> ii;
  18. const int N = 1e6+5;
  19.  
  20. int n,m;
  21. int l[N], conference[N], team[N];
  22. vector<vector<int>> a;
  23. ii p[N];
  24.  
  25. void solve()
  26. {
  27. 	// Ghi lại thời điểm bắt đầu chương trình
  28. 	auto start = clock();
  29. 	// Input
  30. 	cin>>n>>m;
  31. 	a.resize(n+1);
  32. 	for (int i = 1; i <= m; i++) cin>>p[i].fi>>p[i].se;
  33. 	int mx = 0; // Lưu nhóm có index lớp nhất
  34. 	for (int i = 1; i <= n; i++) 
  35. 	{
  36. 		cin>>l[i];
  37. 		a[i].resize(l[i]);
  38. 		for (int j = 0; j < l[i]; j++) cin>>a[i][j], mx = max(mx, a[i][j]);
  39. 	}
  40. 	while (true) 
  41. 	{
  42. 		if (clock() - start > 4950) break; // Kiểm tra xem đến lần duyệt này đã vượt quá thời gian cho phép hay chưa
  43. 		// Gán mỗi người 1 nhóm bất kì trong wishlist của người đó
  44. 		for (int i = 1; i <= n; i++) team[i] = a[i][rnd(0, l[i]-1)]; 
  45. 		// Phân chia các nhóm vào các bảng đấu một cách random
  46. 		for (int i = 1; i <= mx; i++) conference[i] = rnd(1,2);
  47. 		// Đếm số lượng cặp ghét nhau
  48. 		int cnt = 0;
  49. 		for (int i = 0; i < m; i++) 
  50. 		{
  51. 			int x = p[i].fi, y = p[i].se;
  52. 			if (conference[team[x]] != conference[team[y]]) cnt++;
  53. 		}
  54. 		// Nếu cách xếp này thỏa mãn thì in ra
  55. 		if (cnt * 2 >= m) 
  56. 		{
  57. 			for (int i = 1; i <= n; i++) cout<<team[i]<<" ";
  58. 			cout<<"\n";
  59. 			for (int i = 1; i <= mx; i++) cout<<conference[i]<<" ";
  60. 			return;
  61. 		}
  62. 	}
  63. }
  64.  
  65. int main()
  66. {
  67. 	solve();
  68. }
Success #stdin #stdout 0s 5628KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/Po4jDm
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
9 days 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!