oj.uz

Submission #847615

# Submission time Handle Problem Language Result Execution time Memory
847615 2023-09-10T04:37:35 Z AndriaBeridze Odd-even (IZhO11_oddeven) C++14
0 / 100
 2 ms 600 KB 
#include<bits/stdc++.h>

using namespace std;
int TC = 0;

void dbg_out() {cout << endl;}
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {cout << " " << H; dbg_out(T...);}
#define debug(...) {cout << "(" << #__VA_ARGS__ << "):"; dbg_out(__VA_ARGS__);}

#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define add push_back
#define size(v) (int) v.size()
#define left node * 2, l, (l + r) / 2
#define right node * 2 + 1, (l + r) / 2 + 1, r
#define check() cout << "Why doesn't this stupid a** code work?" << endl;
#define inf (int) 1e18

struct longint{
    vector<int> d;
public:
    longint(int n){
        d = vector<int>(n, 0);
    }
};

longint x(55);
longint one(55);

bool bigger(longint a, longint b){
    for(int i = 0; i < 55; i++){
        if(a.d[i] > b.d[i]) return true;
        if(a.d[i] < b.d[i]) return false;
    }
    return true;
}

longint multiply(longint a, longint b){
    longint ans(55);
    for(int i = 0; i < 55; i++){
        for(int j = 0; j < 55; j++){
            int ind = 54 - (55 - i - 1) - (55 - j - 1);
            if(ind < 0) continue;
            ans.d[ind] += a.d[i] * b.d[j];
        }
        for(int k = 54; k >= 1; k--){
            ans.d[k - 1] += ans.d[k] / (1000000000);
            ans.d[k] %= (1000000000);
        }
    }
    return ans;
}

longint divide(longint a){
    longint ans(55);
    int k = 0;
    for(int i = 0; i < 55; i++){
        k *= 1000000000;
        k += a.d[i];
        ans.d[i] = k / 2;
        k %= 2;
    }
    return ans;
}

longint add(longint a, longint b){
    longint ans(55);
    for(int i = 0; i < 55; i++){
        ans.d[i] = a.d[i] + b.d[i];
    }
    for(int k = 54; k >= 1; k--){
            ans.d[k - 1] += ans.d[k] / (1000000000);
            ans.d[k] %= (1000000000);
    }
    return ans;
}

longint mod(longint a){
    longint ans(55);
    ans.d[54] = a.d[54] % 2;
    return ans;
}

longint sub(longint a, longint b){
    longint ans(55);
    for(int i = 0;i < 55;i++){
        ans.d[i] = a.d[i] - b.d[i];
        if(ans.d[i]<0){
            ans.d[i] += 1000000000;
            a.d[i + 1]--;
        }
    }
    return ans;
}


void solve(){
    string s;
    cin >> s;
    one.d[54] = 1;
    int t = 54 - size(s) / 9;
    for(int i = 0; i < size(s); i++){
        if(i % 9 == size(s) % 9) t++;
        x.d[t] *= 10;
        x.d[t] += s[i] - '0';
    }
    longint k(55);
    for(int i = 54 - size(s) / 9; i < 55; i++){
        int l = 0, r = 1e9;
        while(l < r){
            int mid = (l + r + 1) / 2;
            k.d[i] = mid;
            if(bigger(divide(multiply(k, add(k, one))), x)) r = mid - 1;
            else l = mid;
        }
        k.d[i] = l;
    }

    bool ok = false;

    x = multiply(x, add(one, one));
    x = sub(x, mod(add(k, one)));
    k = add(divide(k), mod(k));
    x = sub(x, multiply(k, add(one, one)));


    bool ld = false;
    for(int i = 0; i < 55; i++){
        if(ld){
            string p = to_string(x.d[i]);
            while(p.length() != 9){
                p = "0" + p;
            }
            cout << p;
        }
        else if(x.d[i] > 0){
            cout << x.d[i];
            ld = true;
        }
    }
    cout << "\n";
}

signed main(){
    int q = 1;
    //cin >> q;
    while(++TC <= q){
    	solve();
    }
}

Compilation message

oddeven.cpp: In function 'void solve()':
oddeven.cpp:122:10: warning: unused variable 'ok' [-Wunused-variable]
  122 |     bool ok = false;
      |          ^~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Incorrect 2 ms 344 KB Output isn't correct
11 Halted 0 ms 0 KB -