1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <bits/stdc++.h>
using namespace std;
using namespace chrono;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution dist(0, 999999);
bitset<1000000> conflict;
array<array<vector<int>, 10>, 10> post;
int getItem(){
int x;
do{
x = dist(gen);
}while(conflict[x]);
return x;
}
void putItem(int item){
int col = item / 100000,
row = item / 010000 % 10;
auto& r = post[col][row];
r.insert(lower_bound(r.begin(), r.end(), item), item);
}
int findItem(int item){
int col = item / 100000,
row = item / 010000 % 10;
auto& r = post[col][row];
return distance(r.begin(), lower_bound(r.begin(), r.end(), item));
}
int main(){
int n;
cout << "How much item you want to insert? ";
cin >> n;
auto b = high_resolution_clock::now();
while(n--){
int item = getItem();
cout << item << " ";
putItem(item);
}
auto e = high_resolution_clock::now();
auto d = duration_cast<milliseconds>(e-b);
cout << endl << "Cost " << d.count() << "ms" << endl;
while(true){
int i;
cout << "What item you want to find? ";
cin >> i;
b = high_resolution_clock::now();
cout << i/100000 << "-" << i/10000%10 << "-" << findItem(i) << endl;
e = high_resolution_clock::now();
d = duration_cast<milliseconds>(e-b);
cout << "Cost " << d.count() << "ms" << endl;
}
return 0;
}
|