fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cmath>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <utility>
  9. #include <queue>
  10. #include <list>
  11. #include <stack>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <set>
  15. #include <climits>
  16. #include <functional>
  17. using namespace std;
  18. #define PR(x) cout << #x " = " << x << "\n";
  19. typedef vector<int> vi; 
  20. typedef vector<vi> vvi; 
  21. typedef pair<int,int> ii; 
  22. #define sz(a) int((a).size()) 
  23. #define pb push_back 
  24. #define all(c) (c).begin(),(c).end() 
  25. #define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 
  26. #define present(c,x) ((c).find(x) != (c).end()) 
  27. #define cpresent(c,x) (find(all(c),x) != (c).end()) 
  28. #define REP(i,n) for( int i =0 ; i < n ; i++ )
  29. int n,m,c;
  30. int v[100005];
  31.  
  32. int calcmiss(int cache_size){
  33. 	list<int> l;
  34. 	unordered_map<int, list<int>::iterator > mp;
  35.  
  36. 	if(cache_size ==0 ){
  37. 		return m;
  38. 	}
  39.  
  40. 	int cost = 0;
  41. 	for (int i = 0; i < m; ++i)
  42. 	{
  43. 		if(l.size() < cache_size){
  44. 			// simply push (first find whether its aldready there or not) and update
  45. 			auto it = mp.find(v[i]);
  46. 			if(it != mp.end()){
  47. 				// already there in the cache
  48. 				auto list_it = it->second;
  49. 				l.erase(list_it);
  50. 				l.push_front(v[i]);
  51. 				mp[v[i]] = l.begin();
  52.  
  53. 			}else{
  54. 				//not there in the cache simply insert it
  55. 				l.push_front(v[i]);
  56. 				mp[v[i]] = l.begin();
  57. 				cost++;
  58. 			}
  59. 		}else{
  60.  
  61. 			auto it = mp.find(v[i]);
  62.  
  63. 			if(it != mp.end()){
  64. 				// its there in the cache
  65. 				auto list_it = it->second;
  66. 				l.erase(list_it);
  67. 				l.push_front(v[i]);
  68. 				mp[v[i]] = l.begin();
  69. 			}else{
  70. 				//remove and insert
  71. 				auto list_it = l.end();
  72. 				list_it--;
  73. 				mp.erase(*list_it);
  74. 				l.pop_back();
  75. 				l.push_front(v[i]);
  76. 				mp[v[i]] = l.begin();
  77. 				cost++;
  78. 			}
  79. 		}
  80. 	}
  81. 	return cost;
  82. }
  83.  
  84. int main(){
  85. 	std::ios_base::sync_with_stdio(false);
  86. 	int t; 
  87. 	cin>>t;
  88.  
  89. 	while(t--){
  90. 		cin>>n>>m>>c;
  91. 		int s=0, e=n;
  92. 		for (int i = 0; i < m; ++i)
  93. 		{
  94. 			cin>>v[i];
  95. 		}
  96.  
  97. 		int steps = log2(n) + 1;
  98. 		while(s<e && steps!=0){
  99. 			int mid = (s+e)/2;
  100. 			int miss = calcmiss(mid);
  101. 			if(miss>c){
  102. 				s = mid + 1;
  103. 			}else{
  104. 				e = mid;
  105. 			}
  106. 			steps -- ;
  107. 		}
  108.  
  109. 		if(calcmiss(s) <= c){
  110. 			cout<<s<<endl;
  111. 		}else{
  112. 			cout<<-1<<endl;
  113. 		}
  114.  
  115. 	}
  116. }
Success #stdin #stdout 0s 3868KB
comments (?)
stdin
copy 
3
5 8 5
1 2 3 4 5 3 4 5
3 3 1
1 1 2
4 5 2
1 2 1 2 1
stdout
copy 
3
-1
2
https://ideone.com/wfuME8
language:
C++14 (gcc 8.3)
created:
10 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!