fork(1) download
copy 
  1. #include <iostream>
  2. #include <list>
  3.  
  4. using namespace std;
  5.  
  6. int main(int argc, char** argv) {
  7.  
  8. 	ios_base::sync_with_stdio(false);
  9. 	cin.tie(NULL);
  10.  
  11. 	int n, m, curr, temp;
  12. 	int result = 0;
  13. 	int pos2 = 0, pos3 = 0;
  14. 	list<int>::iterator it;
  15.  
  16. 	cin >> n;
  17. 	list<int> mylist;
  18. 	for(int i = 1; i <= n; i++){
  19. 		mylist.push_back(i);
  20. 	}
  21.  
  22. 	cin >> m;
  23.  
  24. 	while(m > 0){
  25. 		cin >> curr;
  26. 		// cout << "curr = " << curr << "\n";
  27. 		// 큐의 front에 뽑고자 하는 원소가 있을 경우 
  28. 		if(mylist.front() == curr){
  29. 			mylist.pop_front();
  30. 		}
  31. 		// 큐의 front에 뽑고자 하는 원소가 없을 경우  
  32. 		else{
  33. 			// 2번 혹은 3번 연산이 이로운지 판별함 
  34. 			pos2 = 0; pos3 = 0;			
  35. 			// 2번은 리스트의 front부터 계산
  36. 			it = mylist.begin();
  37. 			while((*it) != curr){
  38. 				it++;
  39. 				pos2++;				
  40. 			}
  41. 			// 3번은 리스트의 back부터 계산 
  42. 			it = mylist.end();
  43. 			if((*it) == curr){
  44. 				pos3++;
  45. 			} else {
  46. 				while((*it) != curr){
  47. 					it--;
  48. 					pos3++;				
  49. 				}	
  50. 			}
  51. 			// 더 이로운 쪽으로 수행 
  52. 			if(pos3 >= pos2){
  53. 				// 2번 연산
  54. 				while(mylist.front() != curr){
  55. 					temp = mylist.front();
  56. 					mylist.pop_front();
  57. 					mylist.push_back(temp);
  58. 				}
  59. 				mylist.pop_front();
  60. 				result += pos2;
  61. 				// cout << "2, " << pos2 << "\n";
  62. 			} else{
  63. 				// 3번 연산
  64. 				while(mylist.front() != curr){
  65. 					temp = mylist.back();
  66. 					mylist.pop_back();
  67. 					mylist.push_front(temp);
  68. 				}
  69. 				mylist.pop_front();
  70. 				result += pos3;
  71. 				// cout << "3, " << pos3 << "\n";
  72. 			}
  73. 		}
  74.  
  75. 		/*
  76.  
  77. 		for(list<int>::iterator it = mylist.begin(); it != mylist.end(); it++){
  78. 			cout << *it << " ";
  79. 		}
  80. 		cout << "\n\n";
  81.  
  82. 		*/
  83.  
  84. 		m--;
  85. 	}
  86.  
  87. 	printf("%d", result);
  88.  
  89. 	return 0;
  90. }
Success #stdin #stdout 0s 4188KB
comments (?)
stdin
copy 
10 10
4 9 1 7 2 3 10 6 8 5
stdout
copy 
10
https://ideone.com/eG3YEx
language:
C++14 (gcc 8.3)
created:
3 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!