fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 1;
  5. int n, c[N], Next[N], last[N];
  6. queue<int> qu;
  7. bool vis[N];
  8.  
  9. int BFS() {
  10.     if (n == 1)
  11.         return 0;
  12. 	while (!qu.empty())
  13. 		qu.pop();
  14. 	qu.push(0);
  15. 	int cost = 1;
  16. 	while (!qu.empty()) {
  17. 		for (int size = qu.size(); size >= 1; --size) {
  18. 			int cur = qu.front();
  19. 			qu.pop();
  20. 			if (!vis[cur + 1]) {
  21. 				if (cur + 1 == n - 1)
  22. 					return cost;
  23. 				vis[cur + 1] = true;
  24. 				qu.push(cur + 1);
  25. 			}
  26. 			if (Next[cur] != -1 && !vis[Next[cur]]) {
  27. 				if (Next[cur] == n - 1)
  28. 					return cost;
  29. 				vis[Next[cur]] = true;
  30. 				qu.push(Next[cur]);
  31. 			}
  32. 		}
  33. 		++cost;
  34. 	}
  35. 	assert(false);
  36. 	return -1;
  37. }
  38.  
  39. int main(int argc, char **argv) {
  40. 	int t;
  41. 	scanf("%d", &t);
  42. 	while (t-- != 0) {
  43. 		scanf("%d", &n);
  44. 		for (int i = 0; i < n; ++i)
  45. 			scanf("%d", &c[i]);
  46. 		memset(last, -1, sizeof last);
  47. 		for (int i = 0; i < n; ++i)
  48. 			vis[i] = false;
  49. 		for (int i = n - 1; i >= 0; --i) {
  50. 			Next[i] = last[c[i]];
  51. 			last[c[i]] = i;
  52. 		}
  53. 		printf("%d\n", BFS());
  54. 	}
  55. 	return 0;
  56. }
Runtime error #stdin #stdout #stderr 0s 18608KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
prog: prog.cpp:35: int BFS(): Assertion `false' failed.
https://ideone.com/P2yACH
language:
C++ (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!