fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define isz(x) (int)(x).size()
  3. typedef std::pair<int,int> pii;
  4. typedef long long ll;
  5.  
  6. namespace Solution {
  7. 	const ll MAX = 100000LL * 100000;
  8. 	ll squares[1+100000LL];
  9. 	std::vector<ll> queries;
  10. 	std::vector<pii> answers;
  11. 	void init(const std::vector<ll>& queries_) {
  12. 		queries = queries_;
  13. 		answers.resize(isz(queries));
  14. 		for (int i = 0; i <= 100000LL; ++i) {
  15. 	        squares[i] = 1LL * i * i;
  16. 	    }
  17. 	}
  18. 	pii solve_one(const ll p) {
  19. 		int back = 100000;
  20.         for (int i = 1; i <= back && squares[i] <= p; ++i) {
  21.             while (squares[i] + squares[back] > p) { --back; }
  22.             if (squares[i] + squares[back] == p) {
  23.                 return pii(i,back);
  24.             }
  25.         }
  26.         return pii(0,0);
  27. 	}
  28. 	void solve_all() {
  29. 		for (int i = 0; i < isz(queries); ++i) {
  30. 			answers[i] = solve_one(queries[i]);
  31. 		}
  32. 	}
  33. }
  34.  
  35. void worst_test(int n) {
  36. 	Solution::init(std::vector<ll>(n, Solution::MAX-1));
  37. 	Solution::solve_all();
  38. 	assert(Solution::answers[n/2].first != -2);
  39. 	std::exit(0);
  40. }
  41.  
  42. int main() {
  43. 	//worst_test(10000);
  44.     std::ios_base::sync_with_stdio(false);
  45.     std::cin.tie(0);
  46.     int t; std::cin >> t;
  47.     std::vector<ll> queries(t);
  48.     for (auto &it : queries) { std::cin >> it; }
  49.     Solution::init(queries);
  50.     Solution::solve_all();
  51.     for (int i = 0; i < t; ++i) {
  52.     	auto res = Solution::answers[i];
  53.     	std::cout << "Case " << i+1 << ": ";
  54.         if (res.first == 0 || res.second == 0) {
  55.             std::cout << "Impossible\n";
  56.         } else {
  57.             std::cout << res.first << " " << res.second << "\n";
  58.         }
  59.     }
  60.     return 0;
  61. }
Success #stdin #stdout 0s 16016KB
comments (?)
stdin
copy 
3
2
11
13
stdout
copy 
Case 1: 1 1
Case 2: Impossible
Case 3: 2 3
https://ideone.com/qSBbzq
language:
C++14 (gcc 8.3)
created:
5 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!