oj.uz

Submission #522690

# Submission time Handle Problem Language Result Execution time Memory
522690 2022-02-05T11:49:22 Z Be_dos Odd-even (IZhO11_oddeven) C++17
100 / 100
 2 ms 332 KB 
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

#define BASE 1000

struct BigInt {
    int32_t data[100];

    BigInt() {
        for(int32_t i = 0; i < 100; i++)
            data[i] = 0;
    }

    BigInt(std::string str) {
        for(int32_t i = 0; i < 100; i++)
            data[i] = 0;
        int32_t next = 0;
        int32_t mult = 1;
        for(int32_t i = str.size() - 1; i >= 0; i--) {
            data[next] += (str[i] - '0') * mult;
            mult *= 10;
            if(mult == BASE) {
                mult = 1;
                next++;
            }
        }
    }

    BigInt operator+(int32_t x) {
        BigInt res = *this;
        res.data[0] += x;
        for(int32_t i = 0; i < 100; i++) {
            if(res.data[i] < BASE)
                return res;
            res.data[i] = 0;
            res.data[i + 1]++;
        }
    }

    BigInt operator-(int32_t x) {
        BigInt res = *this;
        res.data[0] -= x;
        for(int32_t i = 0; i < 100; i++) {
            if(res.data[i] >= 0)
                return res;
            res.data[i] += BASE;
            res.data[i + 1]--;
        }
    }

    BigInt operator+(BigInt other) {
        BigInt res;
        for(int32_t i = 0; i < 100; i++)
            res.data[i] = data[i] + other.data[i];
        for(int32_t i = 0; i < 99; i++) {
            res.data[i + 1] += res.data[i] / BASE;
            res.data[i] %= BASE;
        }
        return res;
    }

    BigInt operator-(BigInt other) {
        BigInt res;
        for(int32_t i = 0; i < 100; i++)
            res.data[i] = data[i] - other.data[i];
        for(int32_t i = 0; i < 99; i++) {
            if(res.data[i] < 0) {
                res.data[i] += BASE;
                res.data[i + 1]--;
            }
        }
        return res;
    }

    BigInt operator*(BigInt other) {
        BigInt res;
        for(int32_t i = 0; i < 50; i++)
            for(int32_t j = 0; j < 50; j++)
                res.data[i + j] += data[i] * other.data[j];
        for(int32_t i = 0; i < 99; i++) {
            res.data[i + 1] += res.data[i] / BASE;
            res.data[i] %= BASE;
        }
        return res;
    }

    BigInt half() {
        BigInt res;
        for(int32_t i = 99; i >= 0; i--) {
            res.data[i] += data[i] / 2;
            if(i > 0)
                res.data[i - 1] += (data[i] % 2) * (BASE / 2);
        }
        return res;
    }

    void output() {
        bool started = false;
        for(int32_t i = 99; i >= 0; i--) {
            std::string cur = std::to_string(data[i]);
            if(data[i] == 0 && !started)
                continue;
            if(started)
                while(cur.size() < 3)
                    cur = "0" + cur;
            started = true;
            std::cout << cur;
        }
    }

    bool operator<(BigInt other) {
        for(int32_t i = 99; i >= 0; i--)
            if(data[i] != other.data[i])
                return data[i] < other.data[i];
        return false;
    }
};

BigInt int_sqrt(BigInt n) {
    BigInt left, right = BigInt(std::string(100, '9'));
    while(BigInt("1") < right - left) {
        BigInt m = (left + right).half();
        if(m * m < n)
            left = m;
        else
            right = m;
    }
    return right;
}

int main() {
    std::string n_str;
    std::cin >> n_str;

    BigInt n(n_str);

    BigInt block = (int_sqrt(n * BigInt("8") + 1)).half();
    BigInt block_end = (block * (block + 1)).half();
    BigInt block_start = block_end - block + 1;
    BigInt ans = block_start + ((block - 1) * (block - 2)).half() + (n - block_start) * BigInt("2");
    ans.output();
    return 0;
}

//0  0        1           3                 6                 10
//1,  2, 4,   5, 7, 9,    10, 12, 14, 16,   17 19 21 23 25    26
//1   2  3    4  5  6     7   8    9  10    11 12 13 14 15    16

Compilation message

oddeven.cpp: In member function 'BigInt BigInt::operator+(int32_t)':
oddeven.cpp:58:5: warning: control reaches end of non-void function [-Wreturn-type]
   58 |     }
      |     ^
oddeven.cpp: In member function 'BigInt BigInt::operator-(int32_t)':
oddeven.cpp:69:5: warning: control reaches end of non-void function [-Wreturn-type]
   69 |     }
      |     ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 272 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 288 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 288 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 292 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 2 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 2 ms 204 KB Output is correct
22 Correct 2 ms 292 KB Output is correct