Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/detail/standard_policies.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5.  
  6. #define pb push_back
  7. #define F first
  8. #define S second
  9. #define ll long long
  10. #define FILE "t9"
  11. #define ld long double
  12. #define endl '\n'
  13. #define pii pair <int, int>
  14. #define last fedgfre
  15. #define ull unsigned long long
  16. //#define int long long
  17.  
  18. //#pragma comment(linker, "/stack:200000000")
  19. //#pragma GCC optimize("Ofast")
  20. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  21. //#pragma GCC optimize("unroll-loops")
  22.  
  23. using namespace std;
  24. using namespace __gnu_pbds;
  25.  
  26. #define kek pair <pii, int>
  27.  
  28. typedef tree <kek,null_type,less<kek>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  29.  
  30. const int N = 1e5 + 5;
  31. const ll mod = 998244353;
  32. const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1 };
  33. const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1 };
  34. const ld pi = acos(-1.0);
  35. const int B = (int)sqrt(N);
  36.  
  37. const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
  38. const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};
  39.  
  40. mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
  41.  
  42. int a[N];
  43.  
  44. int main() {
  45. ios_base::sync_with_stdio(0);
  46. cin.tie(0);
  47. cout.tie(0);
  48. // srand(time(0));
  49. #ifdef LOCAL
  50. freopen("input.txt", "r", stdin);
  51. freopen("output.txt", "w", stdout);
  52. #else
  53. // freopen(FILE".in", "r", stdin);
  54. // freopen(FILE".out", "w", stdout);
  55. #endif // LOCAL
  56. int n;
  57. cin >> n;
  58. if (n == 1){
  59. cout << 1;
  60. return 0;
  61. }
  62. vector <pii> q;
  63. for (int i = 0; i < n; i += 2) {
  64. q.pb({i, i + 1});
  65. }
  66. int cnt = n / 2;
  67. for (int i = 0; i < n - 1; i++) cin >> a[i];
  68. int last = 0;
  69. while (cnt) {
  70. vector <int> win;
  71. int it = 0;
  72. for (int i = last; i < last + cnt; i++) {
  73. if (a[i] == 1) win.pb(q[it].F);
  74. else win.pb(q[it].S);
  75. it++;
  76. }
  77. q.clear();
  78. if (cnt == 1) {
  79. cout << win[0] + 1;
  80. return 0;
  81. }
  82. for (int i = 0; i < win.size(); i += 2) {
  83. q.pb({win[i], win[i + 1]});
  84. }
  85. last += cnt;
  86. cnt >>= 1;
  87. }
  88. return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement