Geome try/codechef ENC2020F

Ссылки сюда (1) →

codechef/ENC2020F

#include <bits/stdc++.h>
 
constexpr size_t DIV_CNT = 100000 + 1;
 
enum class UpdateKind {
    APPEND, DELETE,
};
 
void update_divs(uint64_t num, std::vector<uint64_t>& divs, std::set<size_t>& divs_set,
                 const std::vector<std::vector<uint64_t>>& divs_map, UpdateKind kind) {
    for (auto div : divs_map[num]) {
        switch (kind) {
            case UpdateKind::APPEND: {
                ++divs[div];
                if (divs[div] == 2) {
                    divs_set.insert(div);
                }
                break;
            }
            case UpdateKind::DELETE: {
                --divs[div];
                if (divs[div] == 1) {
                    divs_set.erase(div);
                }
                break;
            }
            default: {
                __builtin_unreachable();
            }
        }
    }
}
 
int main() {
    std::vector<std::vector<uint64_t>> divs_map(DIV_CNT);
    for (uint64_t num = 1; num < DIV_CNT; ++num) {
        for (uint64_t idx = num; idx < DIV_CNT; idx += num) {
            divs_map[idx].push_back(num);
        }
    }
 
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    size_t cnt = 0, qcnt;
    std::cin >> cnt >> qcnt;
    std::vector<uint64_t> nums(cnt);
    std::vector<uint64_t> divs(DIV_CNT);
    std::set<size_t> divs_set;
    for (auto& num : nums) {
        std::cin >> num;
        update_divs(num, divs, divs_set, divs_map, UpdateKind::APPEND);
    }
 
    std::vector<uint64_t> ans_vec;
    while (qcnt--) {
        int type = 0;
        std::cin >> type;
        switch (type) {
            case 1: {
                size_t idx = cnt;
                uint64_t curr = 0;
                std::cin >> idx >> curr;
                auto prev = nums[idx];
                nums[idx] = curr;
                update_divs(prev, divs, divs_set, divs_map, UpdateKind::DELETE);
                update_divs(curr, divs, divs_set, divs_map, UpdateKind::APPEND);
                break;
            }
            case 2: {
                uint64_t ans = (divs_set.empty() ? 1 : *std::prev(std::end(divs_set)));
                ans_vec.push_back(ans);
                break;
            }
            default: {
                __builtin_unreachable();
            }
        }
    }
 
    for (auto ans : ans_vec) {
        std::cout << ans << '\n';
    }
 
    return 0;
}

StasFomin 02:40, 19 мая 2022 (UTC): Вы невнимательны и игнорировали и курс и задания. Решения ожидается только на Python.

Концептуально:

• Win-Win!
• Абсолютно практические задачи с собеседований.
  • LeetCode
  • CodeChef
  • SpojCode
  • Сотни решенных и нерешенных
• Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
• Нужно быть залогиненным
  • Скрыто из интернета
• Изучайте Решенные практические задачи (Их там 1027)
• Надо решить N задач из 4 разных разделов. На Python.
  • 8 если до 2024-03-08
  • 12 если до 2024-04-08
  • 16 если до 2024-05-08
• За задачи из CodeChef и SpojCoding будут дополнительные бонусные очки (2 балла из настоящей 10 бальной оценки!), их решать сложнее, там не подсказывают тест вызвавший ошибку, там могут быть жесткие TL, надо больше стараться, и да, их надо решать именно на Python (любом, который есть на сервисе, хоть PyPy) оптимизировать вам могут помочь статьи:
  • Blog:Advanced_Algorithms/Python-оптимизация_жадного_алгоритма_из_codechef
  • Blog:Advanced_Algorithms/Python-оптимизация_алгоритма_динамического_программирования_из_codechef
  • Blog:Advanced_Algorithms/Путь_хакера_—_решение_задачи_с_codechef_на_питон._С_машинным_кодом
• Бонусные задачи вполне решаются, если их не боятся → вот из последних решений → Участник:Mishaglik/Solutions/Spoj/FRQPRIME

• Выбирайте задачи из Открытые практические задачи, переходите к редактированию по «Беру…» →

• • помечайте их как {{reserve-task|~~~~~}}
• Зарезервированные задачи убираются в Зарезервированные практические задачи

(Их там 55)

• • Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
• Решенное
  • Ну смотрите, как оформлено в прошлые годы
  • Решение на подстранице вашей личной страницы
    • Вики-ссылка на задачу
    • Python-код в «<source lang="python"></source>»
    • Метка «{{checkme}}», когда решите.

• • • Внизу вставка всего этого по клику →
• Они попадут в Категория:На проверку

(Их там 10)

• Как легче решать Python
  • Загрузка данных
  • Выбирайте более свежий CPython или PyPy.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.