Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 简单提一句，如果先用set，可以过2200ms+；但是先用set得到500000间最大值以后hash桶，16ms

Posted by 947186602 at 2020-09-06 15:15:22 on Problem 2081
```#include<cstdio>
#include<set>
#include<string.h>
using namespace std;
const int MAX_K = 500005;
int number[MAX_K];
int k;

//使用set 2297ms
void init(){
set<int> remember;
number[0] = 0;
remember.insert(0);
int res = 0;
for(int i = 1;i < MAX_K;++i){
int now = number[i-1] - i;
if(now < 0 || remember.count(now) == 1){
now = number[i-1] + i;
//printf("%lld\n",now);
}
number[i] = now;
remember.insert(now);
res = res > now ? res : now;
}
//printf("%d\n",res);//3012500
}
//知道最大值了，直接hash桶就完事了 16ms
bool use[3012505];
void init2(){
number[0] = 0;
memset(use,false,sizeof(use));
use[0] = true;
for(int i = 1;i < MAX_K;++i){
int now = number[i-1] - i;
if(now < 0 || use[now] == true){
now = number[i-1] + i;
}
number[i] = now;
use[now] = true;
}
}
int main(){
init2();
while(~scanf("%d",&k) && k != -1){
printf("%d\n",number[k]);
}
return 0;
}```

Followed by: