1. C++ / Говнокод #19028

    +5

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    #include <bits/stdc++.h>
    using namespace std;
    #define mp make_pair
    #define mt make_tuple
    #define pb push_back
    #define rep(i,a,b) for(int i=a;i<b;++i)
    #define forn(i, n) for(int i=0;i<n;++i)
    #define forv(it, v) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
    #define all(c) (c).begin(), (c).end()
    #define fst first
    #define snd second
    typedef vector<int> vi;
    typedef vector<vi> vvi;
    typedef pair<int,int> pii;
    typedef long long ll;
    typedef vector<ll> vll;
    typedef pair<ll,ll> pll;
    typedef long double ld;
    typedef string st;
    const int inf = 1000 * 1000 * 1000;
    const int mod = 1000 * 1000 * 1000 + 7;
    const ld pi = acos(-1.0);
    const ll infl = 1000ll * 1000ll * 1000ll * 1000ll * 1000ll * 1000ll;
    const ld eps = 1e-7;
    #define y1 y1_dhs

    В продолжении предыдущего ГК: типичное начало олимпиадной проги на С++.

    Запостил: Bobik, 16 Ноября 2015

    Комментарии (89) RSS

    • Среди вышеуказанного наибольшую боль у меня вызывают all(c) и y1.
      Ответить
    • Говноеды, сэр.
      Ответить
    • Зачем long double для результата acos(-1.0), который возвращает double? Олимпиадники не знают, что для long double нужно использовать acos(-1.0l)?
      Ответить
      • А я считаю, что вывод типов литералов должен быть автоматическим. Чтобы 1.0 могло быть и флоатом, и дублем, и лонг дублем, и фикседом.
        Разумеется, выражения для вывода типов в обратную сторону должны соответствовать некоторым правилам.
        Ответить
        • В хаски всё так, как ты описал. Тип числового литерала определяется из контекста. Более того, он может даже стать литералом пользовательского типа (а нелько одного из предопределённых), если для пользовательского типа произведены необходимые определения.
          Например, можно сделать так, что выражения x
          let x = 1 + 2 * 3
          станет типа AstNode со значением
          (Op Plus (Const 1) (Op Mul (Const 2) (Const 3))
          Ответить
        • Автоматическим по типу аргументов?
          Ответить
          • по типу результата или второго аргумента
            например:
            float x = 1.0; // тут выводится, что float
            auto y = x*(2.0+3.0); // тут через ветку x распространяется на прочие ветки, что это float;

            При наличии хитрых перегрузок не работает.

            Грубо говоря, работает только в ветках, внутри которых все функции монотипны (т.е. все аргументы принимают одного типа и возвращают того же типа).
            Ответить
            • В кресты это не всунешь нормально.
              Ответить
              • есть тот же auto и есть темплейты. Всё всунешь, было бы желание
                Ответить
                • Как сделать, чтобы 1.0 имел тип long double?
                  Ответить
                  • http://en.cppreference.com/w/cpp/language/user_literal

                    long double operator "" _ld(long double value) {
                    return value;
                    }

                    1.0_ld будет long double.

                    и функции определять как:
                    template <typename T>
                    std::enable_if<std::is_floating_point<T> ::value, T> func(T value) { ... }

                    Такая функция вернет значение передаваемого в неё аргумента типа с плавающей точкой.
                    Ответить
                    • Наркоман. Я и так могу написать 1.0l и это будет long double.
                      Ответить
                      • ок. Но так или иначе, любую функцию можно определить чтобы возвращала значение более объемного типа, через enable_if, is_numeric/is_floating_point и conditional
                        Ответить
        • Давно пора разрешить писать олимпиадки на питоне. Не меняя лимитов по времени и памяти, разумеется.
          Ответить
          • Так уже разрешено (по крайней мере, школьникам (по крайней мере, на всех московских олимпидах)).
            Правда, некоторые люди в оргкомитетах настолько сильно любят питон, что вымеряют ограничения по времени и памяти по решению на нём.
            Ответить
          • В зависимости от требований, либо задача будет решаемой на питоне и в то же время решаемой в лоб на си, либо она будет не решаемой на питоне
            Ответить
            • Antervis в http://govnokod.ru/19028#comment305169 написал:
              >> либо задача будет решаемой на питоне и в то же время решаемой в лоб на си,

              А что, си у нас уже не полны по Тьюрингу?
              Ответить
              • "не знаешь что сказать - вспомни дядьку поумнее"?
                Полнота по Тьюрингу не имеет никакого отношения к сабжу
                Ответить
                • Тогда как может быть так, что на питоне задача решаема, а на си - нет?
                  Ответить
                  • прочитайте внимательнее пожалуйста
                    Ответить
                    • По моему у тебя бред там написал. Попробуй еще раз
                      Ответить
                      • "если задача будет решаться на питоне, значит она точно будет решаться на си, причем высоковероятно даже будет решаться на си в лоб. При этом не факт, что если задача будет решаться на си, она вообще может быть решенной на питоне".
                        (в силу быстродействия)
                        Ответить
                        • >> При этом не факт, что если задача будет решаться на си, она вообще может быть решенной на питоне

                          То есть питон не полон по Тьюрингу?
                          Ответить
                          • При чем тут черт подери Тьюринг? Вопрос в быстродействии
                            Ответить
                            • Причем тут, черт подери, быстродействие? Если задача решается за 1000 лет, то она все равно решается (может быть решенной) хоть на питоне, хоть на пхп, хоть на брейнфаке
                              Ответить
                              • на олимпиадах программа должна проходить тесты за какое-то пороговое время. Не проходит - переписывай. Допустим, две программы реализуют один и тот же алгоритм - одна на питоне, вторая на си/бейсике/паскале/фортране/асме (или любом другом не интерпретируемом языке). Реализация на питоне может не пройти там, где пройдет реализация на компилируемом языке
                                Ответить
                                • А если у меня пайпай, и он умеет джит? Тогда пройдет? А если у меня вижал бейсик, и он собирается в пикод, тогда не пройдет?
                                  Ответить
                                  • > А если у меня пайпай

                                    Типичной гонялке тестов наплевать, что у тебя. Ты сабмитишь только код, он выполняется в заранее оговоренной (версии компиляторов, флажки компилиции и т.п.) изолированной среде.

                                    PyPy поможет тебе разве что в Google Code Jam - там тебе на своей машине тесты надо запускать, а судья принимает только файл с ответами.
                                    Ответить
    • мне кажется, или несколько языков так и родились?
      Ответить
    • Как говорил мой знакомый - "нет такой проблемы, которую нельзя решить новым дефайном"
      Ответить
    • > const int inf = 1000 * 1000 * 1000;
      > const ll infl = 1000ll * 1000ll * 1000ll * 1000ll * 1000ll * 1000ll;
      Тяжелый случай.
      Ответить
      • В олимпиадных задачах часто фигурирует 10е9.
        Ответить
        • и год олимпиады

          "дано 2015 х..."
          Ответить
        • Часто видел число 1000000007 - используется для модульной арифметики в задачках на динамику с большим ответом, чтобы не заставлять людей писать длинную арифметику.
          Ответить
          • а как оно используется?
            Ответить
            • "Вася не любит длинные числа, поэтому выведите ответ по модулю 1000000007"
              Ответить
              • А, оно в условии встречается часто...
                А я думал, это хак такой, который позволяет решить некоторые задачи без длинной арифметики, с высокой вероятностью.
                Ответить
                • Да, он и позволяет решать без длинной арифметике.
                  Заменяем LongInt c долгими арифметическими операциями на ModuleInt с относительно быстрыми:
                  struct ModuleInt { 
                      ModuleInt(int _x = 0): x(_x % p) {}
                      operator int() const { return x; }
                      ModuleInt operator+(ModuleInt y) const { return ModuleInt((x+y.x) % p; }
                      ModuleInt operator*(ModuleInt y) const { return ModuleInt((x*y.x) % p; }
                      // и т.д.
                      // с делением не повезло
                  };
                  Ответить
                  • PS. % p в операциях не нужен, ещё есть член int x.
                    Ответить
                  • Классы... На олимпиаде...
                    Ответить
                    • Это уже не классы, это уже структуры нахуй
                      Ответить
                    • struct Point со перегруженными операторами, len и прочим -- вполне нормально.
                      Ответить
                  • > с делением не повезло
                    Деление тоже прекрасно запиливается. Но не так тривиально.
                    Ответить
                    • > Деление тоже прекрасно запиливается
                      Если P простое :) А так да, расширенный алгоритм Евклида.
                      Ответить
                      • > Если P простое :)
                        Если делитель и P взаимно-простые, емнип. Или я туплю?
                        Ответить
                        • > Или я туплю?
                          Да нет, всё так. Просто модуль P обычно известно в компайл-тайме, а делитель известен только в рантайме.

                          К счастью, задачки обычно построены так, что деления не нужно, только сложение и умножение.
                          Ответить
                          • А жаль. Делением можно было бы затроллить как минимум половину олимпиадников...
                            Ответить
                            • Их и бинпоиском можно треть затроллить (в общем, как и комментаторов ГК, что где-то полгода назад было видно). При чём ЦА задачи про бинпоиск сильно лучше поддастся троллингу, чем ЦА задачи про обратное по модулю.
                              Ответить
                              • >>Их и бинпоиском можно треть затроллить

                                и сортировкой пузырьком
                                Ответить
                              • > бинпоиском
                                Да можно ещё проще - средним арифметическим джвух int'ов.

                                Очевидно, что среднее арифметическое двух int'ов влезает в int. Нужно написать функцию, которая его возвращает :)
                                Ответить
                                • Это относится и к бинпоиску :)
                                  Кстати, мы в школе проходим эту ошибку.
                                  Ответить
                                  • > Это относится и к бинпоиску :)
                                    В 99.9% случаев в бинпоиске все числа неотрицательные и b > a, поэтому можно смело писать a + (b - a) / 2.
                                    Ответить
                                    • Если бинпоиск по массиву, то да. Тогда в 99.9% из этих случаев a и b будут меньше миллиарда, и сойдёт (a+b)/2
                                      А если в программе есть массив на миллиард элементов, по которому делается бинпоиск, то, наверно, чинить надо не среднее, а крышу.
                                      Ответить
                                      • Сколько ж этот массив сортировали... Ну хотя, с другой стороны, N * log(N) это не так уж и много по сравнению с N. Всего раз в 30 разница на этом массиве.
                                        Ответить
                                • Кстати, на ассемблере такую задачу решить даже проще, чем на сишке.
                                  Ответить
                                  • > на ассемблере такую задачу решить даже проще
                                    Но под каждую платформу придётся решать её заново...
                                    Ответить
                                    • Я что то не врубаюсь как вернуть интом среднее арифметическое 1 и 2 на любой платформе
                                      Ответить
                                      • Никак: у 1 и 2 нет среднего арифметического, представимого в int.
                                        В противном случае разобрать два варианта, и либо вернуть a + (b - a) / 2, либо (a + b) / 2
                                        Ответить
                                        • Спасибо, капитан
                                          Но я не втупляю в разговор двух господ - мистера Г и мистера Б
                                          Ответить
                                          • Вариант 1: a+b не переполняется. Тогда надо вернуть (a+b)/2
                                            Вариант 2: a+b переполняется. Тогда надо вернуть a + (b-a)/2, так как b-a в таком случае не переполняется.
                                            Для проверки на переполняемость можно, например, посмотреть старший бит (a>>1)+(b>>1)+(a&b&1)
                                            Ответить
                                            • А ещё для выбора между вариантом 1 и вариантом 2 можно анализировать значения a<b, a<0 и b<0. Из них будет понятно, какую операцию можно использовать без переполнения.
                                              Ответить
                                            • а теперь осталось сделать среднее арифметическое N int ов
                                              Ответить
                                      • Ну пусть будет floor((a+b)/2), для определённости.

                                        P.S. А вообще - на всяких собеседованиях специально вопрос задают в размытой форме, чтобы ты спросил "а как вернуть среднее арифметическое 1 и 2". Если спросил - получишь плюсик в карму. Так что всё ок.
                                        Ответить
                                      • (a&b) + ((a^b)>>1)
                                        Ответить
                                        • Сдвиг вправо для signed не особо определён.
                                          Ответить
                                          • If E1 has a signed type and a negative value, the resulting value is implementation-defined.
                                            Ответить
                    • Оно становится нематематичным: a/b/c % p != a / (bc) % p. А зачем такое нужно и какой смысл оно несёт?
                      Ответить
                      • Что значит "нематематичным"?

                        > a/b/c % p != a / (bc) % p
                        Да ну? Пример в студию или слив засчитан (для b, c, bc взаимнопростых с p само собой).
                        Ответить
                        • >для b, c, bc взаимнопростых с p само собой
                          Если так, то сливаюсь.
                          Ответить
    • Зачем тащить сюда код олимпиадников?

      У них нет цели писать красивый код. Им надо быстро реализовать алгоритм, часто стандартный но с небольшими отклонениями.

      Олимпиадное программирование это как олимпиадная математика - с реальными задачами пересекается редко.
      Ответить
      • >> У них нет цели писать красивый код.

        так у нас нет цели собирать красивый код. Это говнокод. От слова говно. Секешь?
        Ответить
        • Но собирать код, в котором заведомо находится говно, как-то неспортивно. Ты бы ещё предложил собирать исходники CMS или программы для бухгалтерии.
          Ответить
          • Хорошо, дадим автору фору в 2 года - если не исправиться - будем постить его код
            Ответить
    • ещё в детстве так школьников тралил
      Ответить
      • Александреску, ты?
        Ответить
        • А D тут при чем? (не в теме)
          Ответить
          • Александреску таки сначала был крестоблядью: google://Loki
            Ответить
            • Собственно он и вывел крестоблядство на новый уровень, а сам съебал пилить D.
              Ответить
          • александреску это не только шаблоны на крестах..)
            Ответить
    • Так альтернативы сему все равно нет
      Ответить

    Добавить комментарий