Submission #523290

#TimeUsernameProblemLanguageResultExecution timeMemory
523290RaresFelixOdd-even (IZhO11_oddeven)C++17
100 / 100
2 ms296 KiB
#include <bits/stdc++.h>

using namespace std;
const int MC = 271;

struct Big {
    int len, V[MC];
    void read() {
        string s;
        cin >> s;
        len = s.size();
        for(int i = len; i >= 1; --i)
            V[i] = s[len - i] - '0';
    }
    Big() {
        len = 0;
        memset(V, 0, sizeof(V));
    }

    void pune(int v) {
        len = 0;
        memset(V, 0, sizeof(V));
        while (v)
            V[++len] = v % 10, v /= 10;
    }

    void ref() {
        int tr = 0;
        for (int i = 1; i <= len; ++i) {
            V[i] += tr;
            tr = 0;
            if (V[i] >= 10)
                tr = V[i] / 10;
            else if (V[i] < 0){
                while(V[i] < 0)
                    --tr, V[i] = V[i] + 10;
            }
            V[i] %= 10;
        }
        while (tr) V[++len] = tr % 10, tr /= 10;
        while (len && !V[len]) --len;
    }

    Big operator*(const Big &b) const {
        Big re;
        for (int i = 1; i <= len; ++i)
            for (int j = 1; j <= b.len; ++j)
                re.V[i + j - 1] += V[i] * b.V[j];
        re.len = len + b.len - 1;
        re.ref();
        return re;
    }

    Big operator*(const int &v) const {
        Big re;
        for (int i = 1; i <= len; ++i)
            re.V[i] += V[i] * v;
        re.len = len;
        re.ref();
        return re;
    }

    Big operator/(const int &v) const {
        Big re;
        int tr = 0;
        re.len = len;
        for (int i = len; i >= 1; --i)
            tr += V[i], re.V[i] = tr / v, tr %= v, tr *= 10;
        re.ref();
        return re;
    }

    Big operator+(const int &v) const {
        Big re;
        re = (*this);
        re.V[1] += v;
        re.ref();
        return re;
    }

    Big operator-(const int &v) const {
        Big re;
        re = (*this);
        re.V[1] -= v;
        re.ref();
        return re;
    }
    Big operator+(const Big &b) const {
        Big re;
        re.len = max(len, b.len);
        for(int i = 1; i <= len; ++i) re.V[i] += V[i];
        for(int i = 1; i <= b.len; ++i) re.V[i] += b.V[i];
        re.ref();
        return re;
    }
    Big operator-(const Big &b) const {
        Big re;
        re.len = max(len, b.len);
        for(int i = 1; i <= len; ++i) re.V[i] += V[i];
        for(int i = 1; i <= b.len; ++i) re.V[i] -= b.V[i];
        re.ref();
        return re;
    }
    bool operator <(const Big &b) const {
        if(len != b.len) return len < b.len;
        for(int i = len; i >= 1; --i)
            if(V[i] != b.V[i]) return V[i] < b.V[i];
        return 0;
    }
    Big(int v) {
        pune(v);
    }
    void afis() {
        for(int i = len; i >= 1; --i)
            cout << V[i];
        cout << "\n";
    }
};


int main() {
    Big n, st(1), dr, mij, t1, t2;
    n.read();
    dr = n;
    while (st < dr) {
        mij = (st + dr + 1) / 2;
        t1 = mij * (mij + 1);
        t2 = n * 2;
        if (t1 < t2) st = mij;
        else dr = mij - 1;
    }
    Big re = n * 2;
    re = re - st;
    re = re - 1;
    if(!re.len) re.len = re.V[1] = 1;
    re.afis();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...