fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. using namespace std;
  8. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  9. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  10. const int MAXN = (1 << 10);
  11.  
  12. int n;
  13. int a[MAXN][MAXN];
  14.  
  15. void read()
  16. {
  17. 	int v;
  18. 	cin >> v;
  19.  
  20. 	n = sqrt(v);
  21. 	while(n * n < v) n++;
  22. 	while(n * n > v) n--;
  23.  
  24. 	for(int i = 0; i < n; i++)
  25. 		for(int j = 0; j < n; j++)
  26. 			cin >> a[i][j];
  27. }
  28.  
  29. int cnt[MAXN << 13];
  30.  
  31. void solve()
  32. {
  33. 	for(int i = 0; i < n; i++)
  34. 		for(int j = 0; j < n; j++)
  35. 			cnt[a[i][j]]++;
  36.  
  37. 	vector<int> cands;
  38. 	for(int i = 0; i < n; i++)
  39. 		for(int j = 0; j < n; j++)
  40. 		{
  41. 			int x = sqrt(a[i][j]);
  42. 			while(x * x < a[i][j]) x++;
  43. 			while(x * x > a[i][j]) x--;
  44.  
  45. 			if(x * x == a[i][j])
  46. 				cands.push_back(x);
  47. 		}
  48.  
  49. 	sort(cands.begin(), cands.end());
  50.  
  51. 	vector<int> answer;
  52. 	for(int i: cands)
  53. 	{
  54. 		bool ok = 1;
  55. 		for(int j: answer)
  56. 		{
  57. 			if(cnt[i * j] < 2) ok = 0;
  58. 			cnt[i * j] -= 2;
  59. 		}
  60.  
  61. 		if(ok && cnt[i * i])
  62. 		{
  63. 			cnt[i * i]--;
  64. 			answer.push_back(i);
  65. 		}
  66. 		else
  67. 			for(int j: answer)
  68. 				cnt[i * j] += 2;
  69. 	}
  70.  
  71.  
  72. 	for(int i: answer)
  73. 		cout << i << " ";
  74. 	cout << endl;
  75. }
  76.  
  77. int main()
  78. {
  79. 	ios_base::sync_with_stdio(false);
  80. 	cin.tie(NULL);
  81.  
  82. 	read();
  83. 	solve();
  84. 	return 0;
  85. }
  86.  
  87.  
Success #stdin #stdout 0s 52224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
https://ideone.com/SHrk9z
language:
C++14 (gcc 8.3)
created:
6 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!