fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. inline int power(int a, int b) {
  6.     int x = 1;
  7.     while (b) {
  8.         if (b & 1) x *= a;
  9.         a *= a;
  10.         b >>= 1;
  11.     }
  12.     return x;
  13. }
  14.  
  15.  
  16. const int M = 1000000007;
  17. const int N = 3e5+9;
  18. const int INF = 2e9+1;
  19. const int LINF = 2000000000000000001;
  20.  
  21. //_ ***************************** START Below *******************************
  22.  
  23.  
  24. vector<int> a;
  25.  
  26.  
  27. //* Guranteed only 1 soln exists, return index of pair x,y
  28. //* 	Hence [ 3  2 3 x y z 3 ] => freq > 2 can't exist
  29. //* 	Each element will appear once or twice only
  30.  
  31. //* If [ 3  3   4 ] k = 6
  32. //* 	ans = ( firstOccurence , lastOccurence )
  33.  
  34. vector<int> consistency1(int n, int k) {
  35.  
  36.     vector<int> b(a);
  37.  
  38.     //* b[i] => {first, last} occurence (guranteed freq == 1 or == 2)
  39. 	unordered_map<int,vector<int>> mp;
  40. 	for(int i=0; i<n; i++){
  41. 		mp[b[i]].push_back(i);
  42. 	}	
  43. 	sort(begin(b), end(b));
  44.  
  45. 	int s = 0, e = n-1;	
  46. 	while(s<=e){
  47. 		if(b[s] + b[e] == k){
  48. 	        if(b[s] == b[e]){
  49. 	            return {mp[b[s]][0], mp[b[e]][1]};
  50. 	        }
  51. 			return {mp[b[s]][0], mp[b[e]][0]};
  52. 		}
  53. 		else if(b[s] + b[e] > k){
  54. 			e--;
  55. 		}   
  56. 		else s++;
  57. 	}	
  58. 	return {};
  59. }
  60.  
  61.  
  62.  
  63. //* Map alternative 
  64. //* Unique key => {ele , index } 
  65. //* Sort both   {ele, index}[]  by ele
  66.  
  67. vector<int> consistency2(int n, int k) {
  68.  
  69. 	vector<pair<int,int>> b;
  70. 	for(int i=0; i<n; i++){
  71. 	    b.push_back({a[i], i});
  72. 	}
  73. 	sort(begin(b), end(b));	
  74. 	int i = 0, j = n-1;
  75.  
  76. 	while(i<=j){
  77. 	    int sum = b[i].first + b[j].first;
  78. 	    if(sum < k){
  79. 	        i++;
  80. 	    }
  81. 	    else if(sum > k){
  82. 	        j--;
  83. 	    }
  84. 	    else {
  85. 	        return {b[i].second, b[j].second};
  86. 	        break;
  87. 	    }
  88. 	}	
  89.  
  90. 	return {};
  91. }
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105. vector<int> practice(int n, int k) {
  106.  
  107. 	return {-1,-1};
  108. }
  109.  
  110.  
  111.  
  112.  
  113.  
  114. void solve() {
  115.  
  116.     int n, k;
  117.     cin >> n >> k ;
  118.     a.resize(n);
  119.     for(int i=0; i<n; i++) cin >> a[i];
  120.  
  121.     auto ans1 = consistency1(n, k);
  122.     auto ans2 = consistency2(n, k);
  123.     cout << "(" << ans1[0] << "," << ans1[1] << ") , " <<  "(" << ans2[0] << "," << ans2[1] << ") , ";;
  124.  
  125.  
  126.     auto p = practice(n, k);
  127.     // cout << "(" << ans1[0] << "," << ans1[1] << ") , " <<  "(" << p[0] << "," << p[1] << ") , ";;
  128.  
  129. }
  130.  
  131.  
  132.  
  133.  
  134.  
  135. int32_t main() {
  136.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  137.  
  138.     int t = 1;
  139.     cin >> t;
  140.     while (t--) {
  141.         solve();
  142.     }
  143.  
  144.     return 0;
  145. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
2
4 9
2 7 11 15
3 6
3 2 4
stdout
copy 
(0,1) , (-1,-1) , (1,2) , (-1,-1) ,
https://ideone.com/a7rQWE
language:
C++14 (gcc 8.3)
created:
8 hours 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!