// Accept 2456K 16MS 
// 哪位大牛可以在内存2450K的情况下做到0MS,请教一下

#include <iostream>
using namespace std;

const int K = 500000;
int  list[K];

// have相当于一个hash,将某个数做为下标
// mask进行位的俺码计算,用每一个bit来标示该数是否已经存在,以节省内存
// 当然,如果用bool也能做到只用一个bit来标示~

char have[376600];
const int mask[8]={0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};


int main()
{
	bool a = true;
	cout<<sizeof(a)<<endl;
	int n;
	int i;

	memset(list, 0 ,sizeof(list));
	list[0] = 0;
	have[0] |= mask[0];

	for (i=1; i<=K-1; i++)
	{
		list[i]  = list[i-1] - i;
		if (list[i]>0 && !(have[list[i]/8]&mask[list[i]%8]))
		{
			have[list[i]/8] |= mask[list[i]%8];
		}                     
		else
		{
			list[i] = list[i-1] + i;
			have[list[i]/8] |= mask[list[i]%8];
		}
	}
    
	while (scanf("%d", &n) && n!=-1)
	{
		printf("%d\n",list[n]);

	}
    return 0;
}

• Re:2456K内存AC了 (8) ecjtuFFF 2009-02-18 15:50:49
  • Re:2456K内存AC了 (25) 980616701 2009-04-06 12:21:05
• Re:我9020k，0MS AC囧 (119) hustzh 2009-05-27 18:44:14