Advertisement
erek1e

POI Task Chain

Jul 20th, 2022
761
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. struct BigInt {
  7.     static const int MX = 1000;
  8.     int v[MX]{};
  9.     BigInt operator + (const BigInt &b) {
  10.         BigInt c;
  11.         for (int i = 0; i < MX; ++i) c.v[i] = v[i] + b.v[i];
  12.         for (int i = MX-2; i >= 0; --i) {
  13.             c.v[i] += c.v[i+1] / 10;
  14.             c.v[i+1] %= 10;
  15.         }
  16.         return c;
  17.     }
  18.     BigInt (int x) { // x is a digit
  19.         v[MX-1] = x;
  20.     }
  21.     BigInt () {}
  22.     void print() {
  23.         bool seen = false;
  24.         for (int i = 0; i < MX; ++i) {
  25.             if (v[i]) seen = true;
  26.             if (seen) cout << v[i];
  27.         }
  28.         if (!seen) cout << 0;
  29.         cout << endl;
  30.     }
  31. };
  32.  
  33. int main() {
  34.     int n; cin >> n;
  35.     vector<int> a(n);
  36.     for (int &x : a) cin >> x;
  37.     vector<bool> change(n);
  38.     for (int i = n-1; i >= 0; --i) {
  39.         if (a[i] == 1) {
  40.             change[i] = true;
  41.             if (i) a[i-1] = 1-a[i-1];
  42.         }
  43.     }
  44.  
  45.     BigInt sum, pow2(1);
  46.     for (int i = 0; i < n; ++i) {
  47.         if (change[i]) sum = sum + pow2;
  48.         pow2 = pow2 + pow2;
  49.     }
  50.     sum.print();
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement