fork(2) download 
  1. #include<iostream>
  2. #include<set>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. using namespace std;
  6. const int size = 10;//game size
  7. const int times = 10;
  8. const int partyN = 18;
  9. //time , size
  10. int partyBoard[times][size][2] = { 0 };//0 is empty
  11. bool usedParty[times][partyN+1];//1~18, party in this time
  12. bool playedGame[partyN+1][size];//has this party played this game?
  13. set< pair<int, int>  > vs;//party vs party
  14.  
  15. void init()
  16. {
  17.  
  18. 	for (int i = 0; i < times; i++)
  19. 	{
  20. 		for (int j = 0; j < size; j++)
  21. 		{
  22. 			partyBoard[i][j][0] = 0;
  23. 			partyBoard[i][j][1] = 0;
  24. 		}
  25. 		for (int j = 0; j < partyN+1; j++)
  26. 		{
  27. 			usedParty[i][j] = false;
  28. 			playedGame[j][i] = false;
  29. 		}
  30. 	}
  31. }
  32.  
  33.  
  34. void show()
  35. {
  36.  
  37. 	for (int i = 0; i < times; i++)
  38. 	{
  39. 		for (int j = 0; j < size; j++)
  40. 		{
  41. 			if (i != 1)
  42. 				printf(" ");
  43.  
  44. 			printf("(%2d,%2d) ", partyBoard[i][j][0], partyBoard[i][j][1]);
  45.  
  46. 		}
  47. 		printf("\n");
  48. 	}
  49. }
  50.  
  51. //x is game
  52. //y is time
  53. bool backTrack(int x, int y, int r)
  54. {	
  55. //	show();
  56. 	if (x == size)
  57. 	{
  58. 		if (r==0)
  59. 			return backTrack(0, y + 1, partyN);
  60. 		else
  61. 			return false;
  62. 	}
  63. 	if (y == times)
  64. 	{
  65. 		return true;
  66. 	}
  67.  
  68.  
  69. 	for (int i = 1; i < partyN + 1; i++)
  70. 	for (int j = i + 1; j < partyN + 1; j++)
  71. 	{
  72. 		if (usedParty[y][i] == false && usedParty[y][j] == false)//time, party
  73. 		if (playedGame[i][x] == false && playedGame[j][x] == false)//party, game
  74. 		if (vs.count(make_pair(i,j))==0)
  75. 		{
  76.  
  77.  
  78. 			//push
  79. 			partyBoard[y][x][0] = i;
  80. 			partyBoard[y][x][1] = j;
  81. 			usedParty[y][i] = true;
  82. 			usedParty[y][j] = true;
  83. 			playedGame[i][x] = true;
  84. 			playedGame[j][x] = true;
  85. 			vs.insert(make_pair(i, j));
  86.  
  87. 			if (backTrack(x+1,y,r-2))
  88. 			{
  89. 				return true;
  90. 			}
  91.  
  92. 			//pop
  93. 			partyBoard[y][x][0] = 0;
  94. 			partyBoard[y][x][1] = 0;
  95. 			usedParty[y][i] = false;
  96. 			usedParty[y][j] = false;
  97. 			playedGame[i][x] = false;
  98. 			playedGame[j][x] = false;
  99. 			vs.erase(make_pair(i, j));
  100. 		}
  101. 	}
  102.  
  103. 	//skip game
  104. 	if (size-1-x>=r/2)
  105. 	if (backTrack(x+1,y,r))
  106. 		return true;
  107.  
  108. 	return false;
  109. }
  110.  
  111.  
  112.  
  113. int main(int argc, char* argv[])
  114. {
  115.  
  116. 	cout << backTrack(0, 0, 18) << endl;
  117.  
  118. 	show();
  119. 	return 0;
  120. }
  121.  
  122.  
Time limit exceeded #stdin #stdout 5s 3228KB
comments (?)
stdin 
zero
stdout 
Standard output is empty
https://ideone.com/AHWxG0
language:
C++ (gcc 8.3)
created:
8 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!