fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <unordered_set>
  5. using namespace std;
  6. int faulty;
  7.  
  8. int balance(const vector<int> &vl, const vector<int> &vr){
  9. 	// 1 means first param heavy
  10. 	// 2 means invalid measurement
  11. 	if(vl.size()>6||vr.size()>6)	return 2;
  12. 	unordered_set<int> l(vl.begin(), vl.end());
  13. 	unordered_set<int> r(vr.begin(), vr.end());
  14. 	if(l.size()!=vl.size()||r.size()!=vr.size())	return 2;
  15. 	unordered_set<int> o(vl.begin(), vl.end());
  16. 	o.insert(vr.begin(),vr.end());
  17. 	if(o.size()!=l.size()+r.size())	return 2;
  18. 	if(l.size()>r.size())	return 1;
  19. 	if(l.size()<r.size())	return -1;
  20. 	if(l.find(faulty)!=l.end()||r.find(-faulty)!=r.end())	return 1;
  21. 	if(l.find(-faulty)!=l.end()||r.find(faulty)!=r.end())	return -1;
  22. 	return 0;
  23. }
  24. pair<int,int> puzzle_12(){
  25. 	// return value:
  26. 	// {faulty_index, heavy/light}
  27. 	// heavy: 1, light: -1
  28.  
  29. 	vector<int> o = {12,1,2,3};
  30. 	vector<int> b = {4,5,6,7};
  31. 	vector<int> h = {8,9,10,11};
  32.  
  33. 	int x = balance(b,h);	// 1 means first heavy
  34. 	if(x==-1)	swap(b,h);
  35. 	if(x){
  36. 		o.push_back(h[3]);
  37. 		h[3] = b[3];
  38. 		h.push_back(b[2]);
  39. 		x = balance(h,o);
  40. 		if(x==1){
  41. 			h = {b[3]};
  42. 			b = {b[2]};
  43. 			x = balance(b,h);
  44. 			if(x)	return {x==1?b.back():h.back(),1};
  45. 			else	return {o.back(),-1};
  46. 		}
  47. 		else if(x==-1){
  48. 			o = {h[1]};
  49. 			b = {h[2]};
  50. 			x = balance(o,b);
  51. 			if(x)	return {x==1?b.back():o.back(),-1};
  52. 			else	return {h[0],-1};
  53. 		}
  54. 		else{
  55. 			o = {b[0]};
  56. 			h = {b[1]};
  57. 			x = balance(o,h);
  58. 			return {x==1?o.back():h.back(),1};
  59. 		}
  60. 	}
  61. 	else{
  62. 		int O = o.back();
  63. 		o.pop_back();
  64. 		int B = b.back();
  65. 		b.pop_back();
  66. 		x = balance(o,b);
  67. 		if(x){
  68. 			int X = x;
  69. 			O = o.back();
  70. 			o.pop_back();
  71. 			b = {o.back()};
  72. 			o.pop_back();
  73. 			x = balance(o,b);
  74. 			if(x)	return {x==X?o.back():b.back(),X};
  75. 			else	return {O,X};
  76. 		}
  77. 		else{
  78. 			o = {O};
  79. 			b = {B};
  80. 			x = balance(o,b);
  81. 			return {O,x};	// 1 means heavy
  82. 		}
  83. 	}
  84. }
  85. int main() {
  86. 	pair<int,int> p;
  87. 	for(faulty=-12; faulty<=12; faulty++){
  88. 		if(!faulty)	continue;
  89. 		p = puzzle_12();
  90. 		cout<<"Ball at index "<<p.first<<" is "<<(p.second==1?"heavy":"light")<<endl;
  91. 	}
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 4572KB
comments ()
stdin 
Standard input is empty
stdout 
Ball at index 12 is light
Ball at index 11 is light
Ball at index 10 is light
Ball at index 9 is light
Ball at index 8 is light
Ball at index 7 is light
Ball at index 6 is light
Ball at index 5 is light
Ball at index 4 is light
Ball at index 3 is light
Ball at index 2 is light
Ball at index 1 is light
Ball at index 1 is heavy
Ball at index 2 is heavy
Ball at index 3 is heavy
Ball at index 4 is heavy
Ball at index 5 is heavy
Ball at index 6 is heavy
Ball at index 7 is heavy
Ball at index 8 is heavy
Ball at index 9 is heavy
Ball at index 10 is heavy
Ball at index 11 is heavy
Ball at index 12 is heavy
https://ideone.com/dIZtHl
12 balls puzzle.
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!