Posted on 2008-09-22 23:19
superman 阅读(248)
评论(0) 编辑 收藏 引用 所属分类:
URAL
1 /* Accepted 0.312 557 KB */
2 #include <iostream>
3
4 using namespace std;
5
6 const int maxn = 30000;
7
8 template <class T>
9 class Heap
10 {
11 private:
12 T A[maxn + 1]; int len;
13 inline int Parent(int i) { return i / 2; }
14 inline int Lchild(int i) { return i * 2; }
15 inline int Rchild(int i) { return i * 2 + 1; }
16
17 public:
18 Heap(const T * x, const int & n)
19 {
20 len = n;
21 for(int i = 1; i <= n; i++)
22 A[i] = x[i];
23 for(int i = n / 2; i >= 1; i--)
24 modify(i);
25 }
26 Heap(int s, int t)
27 {
28 len = t - s + 1;
29 for(int i = 1; i <= len; i++)
30 A[i] = s + i - 1;
31 }
32 Heap() { len = 0; }
33 void modify(int i)
34 {
35 int min = i;
36 int l = Lchild(i);
37 int r = Rchild(i);
38 if(l <= len && A[l] < A[min]) min = l;
39 if(r <= len && A[r] < A[min]) min = r;
40 if(i != min)
41 {
42 swap(A[i], A[min]);
43 modify(min);
44 }
45 }
46 bool empty() { return len == 0; }
47 T & getmin() { return A[1]; }
48 void push(const T & item)
49 {
50 A[len + 1] = item;
51 int i = len + 1;
52 while(i > 1 && A[i] < A[Parent(i)])
53 {
54 swap(A[i], A[Parent(i)]);
55 i = Parent(i);
56 }
57 len++;
58 }
59 void pop()
60 {
61 swap(A[1], A[len]);
62 len--;
63 modify(1);
64 }
65 bool update(int, int);
66 } ;
67
68 template <class T>
69 bool Heap<T>::update(int num, int latest)
70 {
71 for(int i = 1; i <= len; i++)
72 if(A[i].num == num)
73 {
74 A[i].latest = latest;
75 modify(i);
76
77 return true;
78 }
79 return false;
80 }
81
82 struct rec
83 {
84 int num, latest;
85
86 bool operator < (const rec & x) const
87 {
88 return latest < x.latest;
89 }
90 } ;
91
92 //=============================================
93 int currentTime, accessNum;
94 Heap <int> X(1, 30000);
95 Heap <rec> Y;
96
97 void allocate()
98 {
99 while(Y.empty() == false && currentTime - Y.getmin().latest >= 600)
100 {
101 X.push(Y.getmin().num);
102 Y.pop();
103 }
104
105 cout << X.getmin() << endl;
106 rec r = { X.getmin(), currentTime };
107 Y.push(r);
108 X.pop();
109 }
110
111 void access()
112 {
113 while(Y.empty() == false && currentTime - Y.getmin().latest >= 600)
114 {
115 X.push(Y.getmin().num);
116 Y.pop();
117 }
118
119 cout << (Y.update(accessNum, currentTime) ? '+' : '-') << endl;
120 }
121
122 int main()
123 {
124 char c;
125 while(true)
126 {
127 if(scanf("%d %c", ¤tTime, &c) == EOF)
128 break;
129
130 if(c == '+')
131 allocate();
132 else
133 {
134 scanf("%d", &accessNum);
135 access();
136 }
137 }
138
139 return 0;
140 }