lina_os

Untitled

Jun 19th, 2025
18
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.61 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define ul unsigned long long
  5. #define ld long double
  6. #define vll(v) vector<ll>v
  7. //#define vll(v,n) vector<ll>v(n);
  8. #define mll(m) map<ll,ll>m;
  9. #define sll(s) set<ll>s;
  10. #define iv(v) for(auto &i:v) cin >> i;
  11. #define ov(v) for(auto &i:v) cout << i << " ";
  12. #define all(v) (v.begin(),v.end());
  13. #define Bismillah ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  14.  
  15. using namespace std;
  16.  
  17. string toBin(ll n) {
  18.     string s;
  19.     while (n) {
  20.         s.push_back(n%2+'0');
  21.         n/=2;
  22.     }
  23.     reverse(s.begin(), s.end());
  24.     return s;
  25. }
  26.  
  27. ll mul(ll a, ll b) {
  28.     ll mod=1e9+7;
  29.     return(((a%mod)*(b%mod))%mod);
  30. }
  31.  
  32. ll noz(string s) {
  33.     ll ans=0;
  34.     for (int i=0; i<s.length(); i++) {
  35.         if (s[i]=='0') ans++;
  36.     }
  37.     return ans+(6-s.length());
  38. }
  39.  
  40. ll lw,hg;
  41. bool can(ll i,ll n) {
  42.     if (i*(i+1)/2+n*(n+1)/2 <= hg && i*(i+1)/2+n*(n+1)/2 >= lw) return true;
  43.     return false;
  44. }
  45.  
  46.  
  47. void solve() {
  48.     ll n;
  49.     cin >> n;
  50.     vector<pair<char,ll>>v(n);
  51.     for (int i=0; i<n; i++) {
  52.         cin >> v[i].first >> v[i].second;
  53.     }
  54.  
  55.  
  56.     //a string that has all the bits (10 bits) "xxxxxxxxxx"
  57.     //perform the operations on the bits and replace the x with one or zero if that's the case
  58.     //check if the modified string is the same as the one before the operation
  59.     //combine similar neighbour operators
  60.     //an operation that cancels everything above it? (&0)
  61.     //stack
  62.  
  63.     string s(10,'x');
  64.     stack<pair<char,ll>>l;
  65.     vector<pair<char,ll>>a;
  66.     string pre=s;
  67.     for (int i=0; i<n; i++) {
  68.         char c=v[i].first;
  69.         string bef=s;
  70.  
  71.         if (!l.empty() && l.top().first==c) {
  72.             bef=pre;
  73.             if (c=='|') v[i].second|=l.top().second;
  74.             else if (c=='&') v[i].second&=l.top().second;
  75.             else v[i].second^=l.top().second;
  76.             l.pop();
  77.         }
  78.         string x=toBin(v[i].second);
  79.         reverse (x.begin(), x.end());
  80.         for (int j=0; j<x.size(); j++) {
  81.             if (c=='|') {
  82.                 if (x[j]=='1') s[j]='1';
  83.             }
  84.             else if (c=='^') {
  85.                 if (s[j]!='x') {
  86.                     if (s[j]==x[j]) s[j]='0';
  87.                     else s[j]='1';
  88.                 }
  89.             }
  90.             else {
  91.                 if (x[j]=='0') s[j]='0';
  92.             }
  93.         }
  94.         if (c=='&') {
  95.             for (int j=x.size(); j<10; j++) {
  96.                 s[j]='0';
  97.             }
  98.         }
  99.         if (c=='&' && v[i].second==0) {
  100.             while (!l.empty()) l.pop();
  101.         }
  102.         if (v[i].second==0 && (v[i].first=='|' || v[i].first=='^')) continue;
  103.         if (s.find(string(10,'x'))!=string::npos ||s!=bef ) l.push({c,v[i].second});
  104.         pre=bef;
  105.     }
  106.     a.clear();
  107.     while (!l.empty()) {
  108.         a.push_back(l.top());
  109.         l.pop();
  110.     }
  111.     reverse(a.begin(), a.end());
  112.     cout << a.size() << endl;
  113.     for (auto i:a) cout << i.first << ' ' << i.second << endl;
  114.  
  115.  
  116. }
  117.  
  118. int main() {
  119.     Bismillah
  120.     ll t=1;
  121. //    cin >> t;
  122.     while (t--) {
  123.         solve();
  124.     }
  125.     return 0;
  126. }
  127.  
  128.  
  129. //    ll l,r;
  130. //cin >> l >> r;
  131. //lw=l; hg=r;
  132. //r=(-1+(ll)sqrt(1+8*r))/2;
  133. //ll ans=0;
  134. //for (ll i=1; i<=r; i++) {
  135. //ll x=i, y=r, mn, mx;
  136. //while (x<=y) {
  137. //mn=(x+y)/2;
  138. //if (can(i,mn)) {
  139. //if (mn==1 || !can(i,mn-1)) break;
  140. //else y=mn-1;
  141. //}
  142. //else x=mn+1;
  143. //
  144. //}
  145. //if (!can(i,mn)) continue;
  146. //x=i; y=r;
  147. //while (x<=y) {
  148. //mx=(x+y)/2;
  149. //if (can(i,mx)) {
  150. //if (mx==r || !can(i,mx+1)) break;
  151. //else x=mx+1;
  152. //}
  153. //else y=mx-1;
  154. //}
  155. //
  156. //ans+=mx-mn+1;
  157. //}
  158. //cout << ans << endl;
  159.  
  160.  
Advertisement
Add Comment
Please, Sign In to add comment