Advertisement
GerONSo

Untitled

Apr 9th, 2019
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.22 KB | None | 0 0
  1. #define pragma
  2.  
  3. #ifdef pragma
  4. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
  5. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. #endif // pragma
  7.  
  8. #include<bits/stdc++.h>
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11.  
  12. #define ll long long
  13. #define all(x) begin(x), end(x)
  14. #define pb push_back
  15. #define x first
  16. #define y second
  17. //#define int long long
  18. #define zero(two) memset(two, 0, sizeof(two))
  19.  
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23.  
  24. typedef vector<int> vi;
  25. typedef vector<bool> vb;
  26. typedef pair<int, int> pii;
  27. typedef long double ld;
  28. typedef vector<vi> matrix;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. // cout << fixed << setprecision(10);
  39. #if _offline
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 1e6 + 10;
  46. const int INF = 1e9 + 7;
  47. const int MAXLOG = 20;
  48. const int MOD = 998244353;
  49. const int BASE = 47;
  50.  
  51. vi mn(vi a, vi b) {
  52. vi c = a;
  53. vi d = b;
  54. while(a.size() && a.back() == b.back()) {
  55. a.pop_back();
  56. b.pop_back();
  57. }
  58. if(!a.size()) return c;
  59. if(a.back() < b.back()) {
  60. return c;
  61. }
  62. return d;
  63. }
  64.  
  65. signed main() {
  66. seriy();
  67. int n;
  68. cin >> n;
  69. vector<string> s(n);
  70. vi a(n);
  71. vi cnt(MAXN);
  72. bool f = 0;
  73. vector<vi> r(n);
  74. vi lst(n);
  75. for(int i = 0; i < n; i++) {
  76. cin >> s[i];
  77. reverse(all(s[i]));
  78. int cc = 0;
  79. for(int j = 0; j < s[i].size(); j++) {
  80. r[i].pb(s[i][j] - '0');
  81. if(s[i][j] == '1') {
  82. cc++;
  83. lst[i] = j;
  84. a[i] = j;
  85. }
  86. }
  87. f = f | (cc > 1);
  88. cnt[a[i]]++;
  89. }
  90. if(!f) {
  91. vb used(MAXN);
  92. for(int i = 0; i < MAXN; i++) {
  93. if(cnt[i] > 0) {
  94. used[i] = 1;
  95. cnt[i + 1] += cnt[i] - 1;
  96. }
  97. }
  98. while(used.back() == 0) {
  99. used.pop_back();
  100. }
  101. reverse(all(used));
  102. for(auto i : used) {
  103. cout << i;
  104. }
  105. return 0;
  106. }
  107. while(r[0].size() < r[1].size()) {
  108. r[0].pb(0);
  109. }
  110. while(r[1].size() < r[0].size()) {
  111. r[1].pb(0);
  112. }
  113. r[0].pb(0);
  114. r[0].pb(0);
  115. r[1].pb(0);
  116. r[1].pb(0);
  117. vi ans(r[0].size(), 1);
  118.  
  119. for(int i = 0; i < r[0].size(); i++) {
  120. vector<vi> b = r;
  121. for(int j = 0; j < i; j++) {
  122. b[0][j] = 0;
  123. }
  124. if(i > lst[0] || b[0][i] == 0) {
  125. b[0][i] = 1;
  126. }
  127. else {
  128. continue;
  129. }
  130. // for(auto j : b[0]) {
  131. // cerr << j;
  132. // }
  133. // cerr << '\n';
  134. // for(auto j : b[1]) {
  135. // cerr << j;
  136. // }
  137. // cerr << '\n' << '\n';
  138. vi kek(r[0].size());
  139. bool f = 0;
  140. for(int j = 0; j < b[0].size(); j++) {
  141. f = f | (b[0][j] & b[1][j]);
  142. kek[j] = b[0][j] | b[1][j];
  143. }
  144. if(!f) {
  145. ans = mn(ans, kek);
  146. }
  147. }
  148.  
  149. for(int i = 0; i < r[1].size(); i++) {
  150. vector<vi> b = r;
  151. for(int j = 0; j < i; j++) {
  152. b[1][j] = 0;
  153. }
  154. if(i > lst[1] || b[1][i] == 0) {
  155. b[1][i] = 1;
  156. }
  157. else {
  158. continue;
  159. }
  160. bool f = 0;
  161. vi kek(r[0].size());
  162. for(int j = 0; j < b[1].size(); j++) {
  163. f = f | (b[0][j] & b[1][j]);
  164. kek[j] = b[0][j] | b[1][j];
  165. }
  166. if(!f) {
  167. ans = mn(ans, kek);
  168. }
  169. }
  170. vi kek(r[0].size());
  171. bool fl = 0;
  172. for(int j = 0; j < r[1].size(); j++) {
  173. kek[j] = r[0][j] | r[1][j];
  174. fl = fl | (r[0][j] & r[1][j]);
  175. }
  176. if(!fl) {
  177. ans = mn(ans, kek);
  178. }
  179. while(ans.back() == 0) {
  180. ans.pop_back();
  181. }
  182. while(ans.size()) {
  183. cout << ans.back();
  184. ans.pop_back();
  185. }
  186. return 0;
  187.  
  188. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement