fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using vi = vector<ll>;
  5.  
  6. inline ll mod(ll v, ll m) {
  7. 	return (v % m + m) % m;
  8. }
  9.  
  10. int main() {
  11. 	ll m, n;
  12. 	cin >> m >> n;
  13. 	unordered_set<ll> a;
  14. 	vector<ll> values;
  15. 	for (int i = 0; i < n; ++i) {
  16. 		ll v;
  17. 		cin >> v;
  18. 		a.insert(v);
  19. 		values.push_back(v);
  20. 	}
  21.  
  22. 	random_shuffle(values.begin(), values.end());
  23. 	ll start = values[0];
  24.  
  25. 	if (n == m) {
  26. 		cout << "0 1\n";
  27. 		return 0;
  28. 	}
  29. 	if (n == 1) {
  30. 		cout << start << ' ' << 0 << endl;
  31. 		return 0;
  32. 	}
  33.  
  34. 	vector<pair<ll, ll>> candidates;
  35. 	for (ll v : a) {
  36. 		if (v == start) continue;
  37. 		candidates.push_back({mod(start - v, m), -1});
  38. 		candidates.push_back({mod(v - start, m), -1});
  39. 	}
  40.  
  41. 	int last = -1 + (int)candidates.size();
  42. 	for (ll v : values) {
  43. 		if (last == -1) break;
  44. 		for (int i = 0; i <= last; ++i) {
  45. 			ll nv = v - candidates[i].first;
  46. 			if (nv < 0) nv += m;
  47. 			if (a.find(nv) == a.end()) {
  48. 				if (candidates[i].second < 0)
  49. 					candidates[i].second = v;
  50. 				else {
  51. 					if (last == i) --last;
  52. 					else {
  53. 						swap(candidates[last], candidates[i]);
  54. 						--i;
  55. 						--last;
  56. 					}
  57. 				}
  58. 			}
  59. 		}
  60. 	}
  61.  
  62. 	if (last == -1) cout << -1 << endl;
  63. 	else {
  64. 		if (candidates[last].second < 0) candidates[last].second = start;
  65. 		cout << candidates[last].second << ' ' << candidates[last].first << endl;
  66. 	}
  67.  
  68. 	return 0;
  69. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5 3
1 2 3
stdout
copy 
3 4
https://ideone.com/ggr6Nr
language:
C++14 (gcc 8.3)
created:
7 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!