Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

Из-за вдвое меньшей используемой памяти?

В том числе. Это позволяет переписать циклы, чтобы счетчик инкрементился, а не увеличивался на два. Ну и еще компилятор лучше оптимизирует такие циклы.
Также при просеивании теперь пропускаются четные значения, и само просеивание начинается с i * i (вместо 2-3 * i).

++q*q<n

Это же undefined behavior :)
Я знаю про это, но недостатка в байтах не было. К тому же, нужно как-то найти размер для решета(n / 2 — некошерно).

Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

Да, у меня были далеко не идеальные оптимизации. По правде говоря, я вообще не ожидал, что выиграю.
Я стремился к чему-то такому.

Скрытый текст

//@shadeware
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstdlib>

int main()
{
	//especially for
	http://habrahabr.ru

	//расшифровка предподсчета
	
	long long precalc[66] = {};
	
	for (int i = 0; i < 64 * 7; i++)
	{
		precalc[i / 7 + 2] = precalc[i / 7 + 2] * 96 + "+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL05Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i] - 32;
	}
	
	for (int i = 0; i < 64; i++)
	{
		precalc[i + 2] += 2 * precalc[i + 1] - precalc[i];
	}

	int n;
	scanf("%d", &n);

	long long answer;
	int left;

	if (n & (1 << 23) ) //n ближе к правой границе блока
	{
		answer = -precalc[(n >> 24) + 2];
		//так как answer отрицательный, модуль числа будет уменьшатся
		//при сложении, следовательно, основной код не изменится.
		
		left =  (n >> 24 << 24) + (1 << 24);
		std::swap(left, n);
		++left;
	}
	else //n ближе к левой границе
	{
		left = n >> 24 << 24;

		if (left == 0)
		{
			answer = 2 * (n > 1);
		}
		else
		{
			answer = precalc[(n >> 24) + 1];
		}

	}

	int sq = sqrt(n) + 1e-7;
	
	//уменьшаем в 2 раза все переменные, так как четные числа учитываться не будут 
	
	n = (n - 1) / 2;
	left /= 2;
	sq /= 2;

	std::vector<bool> sieve(sq + 1), block(n - left + 1);
	block[0] = !left;

	//блочное решето
	for (int i = 1; i <= sq; ++i)
	{	
		if (!sieve[i])
		{
			//просеивание до корня
			
			//так как i уменьшено в 2 раза, то исходное i = 2 * i + 1
			//i * i -> 2 * i * (i + 1)
			for (int j = 2 * i * (i + 1); j <= sq; j += 2 * i + 1)
			{
				sieve[j] = 1;
			}

			//просеивание блока

			int j;
			
			//вычисление левой границы, от которой будем просеивать
			if (left == 0)
			{
				j = 2 * i * (i + 1);
			}
			else
			{	
				//находим первое j, которое кратно i && >= left
				j = 2 * (left + i);
				j -= j % (2 * i + 1);

				//просеивать четные числа ни к чему, они будут пропускаться
				if (j % 2 == 0)
				{
					j += 2 * i + 1;
				}
								
				j /= 2;
			}

			for (; j <= n; j += 2 * i + 1)
			{
				block[j - left] = 1;
			}
		}
	}
	
	//подсчет ответа
	for (int i = 0; i <= n - left; ++i)
	{
		if (!block[i])
		{
			answer += i * 2 + left * 2 + 1;
		}
	}
	
	printf("%lld", std::llabs(answer));
}

Данный код работает в худшем случае в ~3 раза быстрее, чем то, что я послал на конкурс. Среднее же время вообще стремится к нулю. И исходник все еще можно обфусцировать до 1024 байт(изменилось не так уж и много).

Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

Скрытый текст

#include <iostream>
#include <algorithm>
#include <string>
#include <iterator>

int main()
{
   std::vector<long long> arr
   ( 
      ( std::istream_iterator<long long>(std::cin) ), 
        std::istream_iterator<long long>() 
   );
   
   for (int i = arr.size() - 1; i > 1; --i)
   {
      arr[i] -= 2 * arr[i - 1] - arr[i - 2];
   }
   
   for (auto x : arr)
   {
      std::string str;
      
      for (; x; x /= 96)
      {  
         str += char(x % 96 + 32);
         
         if ( std::string("\\\"\'").find(str.back()) != std::string::npos)
            str += '\\';
      }
         
      std::cout << std::string(str.rbegin(), str.rend());
   }
}

Результат (на этом же сайте, я, кстати, тестировал свой код).

Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

Впечатляет. Всемогущие хабралюди разгадали мой код быстрее меня самого. И они ни в чем не ошиблись, я лишь добавлю небольшое замечание.
Я заметил, что некоторые люди писали ручные битсеты. Зачем? vector_bool вполне быстр. Когда я ради интереса заменил его на vector_char, скорость просела в несколько раз. Мораль: доверяйте STL.
Также хотелось бы поблагодарить автора конкурса за отличную задачу и современные условия.

Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

Моя идея совпадает с этим комментом.
Только у меня 64 блока и несколько более эффективная реализация(которую, тем не менее, можно еще ускорить в несколько раз, было бы время).
Менее обфусцированный код