Advertisement
Guest User

Untitled

a guest
May 24th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. vector<vector<int>> dp;
  6.  
  7.  
  8. void print(vector<int> v) {
  9. for(int i : v)
  10. cout << i << " ";
  11. }
  12.  
  13. vector<int> paint_back(int x) {
  14. vector<int> result;
  15.  
  16. for (int i = dp[x].size() - 1; i >= 0; i--)
  17. result.push_back(-dp[x][i]);
  18.  
  19. return result;
  20. }
  21.  
  22. void paint_next(int x) {
  23. int prev = x - 1;
  24. int next = x + 1;
  25.  
  26. for (auto i : dp[x])
  27. dp[next].push_back(i);
  28.  
  29. for(auto i : paint_back(prev))
  30. dp[next].push_back(i);
  31.  
  32. dp[next].push_back(next);
  33.  
  34. for(auto i : dp[prev])
  35. dp[next].push_back(i);
  36. }
  37.  
  38.  
  39. int main() {
  40. int n;
  41. cin >> n;
  42.  
  43. if (n == 1) {
  44. cout << 1 << endl;
  45. return 0;
  46. }
  47.  
  48. dp = vector<vector<int>>(n + 1);
  49. dp[1] = {1};
  50. dp[2] = {1, 2};
  51.  
  52.  
  53. for (int i = 2; i < n; i++)
  54. paint_next(i);
  55.  
  56. print(dp[n]);
  57. cout << endl;
  58. return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement