8000 solved 0x17 11286 · jo0n-lab/basic-algo-lecture@c2141fd · GitHub
[go: up one dir, main page]
Skip to content

Commit c2141fd

Browse files
author
cuberry
committed
solved 0x17 11286
1 parent 3c25cd3 commit c2141fd

File tree

12 files changed

+207
-34
lines changed

12 files changed

+207
-34
lines changed

‎0x17/heap_test

16.9 KB
Binary file not shown.

‎0x17/heap_test.cc

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
#include <bits/stdc++.h>
2+
using namespace std;
3+
4+
int heap[100005];
5+
int sz = 0; // heap에 들어있는 원소의 수
6+
7+
void print(){
8+
cout<<"PTINT:: ";
9+
for(int i=1;i<=sz;i++)
10+
cout<<heap[i]<<" ";
11+
cout<<"\n";
12+
}
13+
14+
void push(int x){
15+
heap[++sz]=x;
16+
int idx=sz;
17+
for(int i=sz/2;i>=1;i/=2){
18+
if(heap[i]>x) {
19+
swap(heap[i],heap[idx]);
20+
idx=i;
21+
}
22+
else
23+
break;
24+
}
25+
}
26+
27+
int top(){
28+
if(sz!=0) return heap[1];
29+
else{
30+
cout<<"heap is empty!!\n";
31+
return -1;
32+
}
33+
}
34+
35+
void pop(){
36+
if(sz!=0){
37+
swap(heap[1],heap[sz--]);
38+
int idx=1;
39+
while(idx*2<=sz){
40+
int tar_idx;
41+
if(idx*2+1<=sz)
42+
tar_idx=min_element(heap+2*idx,heap+2*idx+2)-heap;
43+
else tar_idx=idx*2;
44+
if(heap[idx]>heap[tar_idx])
45+
swap(heap[idx],heap[tar_idx]);
46+
else
47+
break;
48+
}
49+
}
50+
else
51+
cout<<"heap is empty\n";
52+
}
53+
54+
void test(){
55+
push(10); push(2); push(5); push(9); // {10, 2, 5, 9}
56+
57+
print();
58+
59+
cout << top() << '\n'; // 2
60+
pop(); // {10, 5, 9}
61+
print();
62+
pop(); // {10, 9}
63+
print();
64+
cout << top() << '\n'; // 9
65+
print();
66+
push(5); push(15); // {10, 9, 5, 15}
67+
print();
68+
cout << top() << '\n'; // 5
69+
print();
70+
pop(); // {10, 9, 15}
71+
cout << top() << '\n'; // 9
72+
}
73+
74+
int main(){
75+
test();
76+
}

‎0x17/heap_test.cpp

Lines changed: 0 additions & 33 deletions
This file was deleted.

‎0x17/heap_test_ans

16.9 KB
Binary file not shown.

‎0x17/heap_test_ans.cpp renamed to ‎0x17/heap_test_ans.cc

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,13 @@ using namespace std;
44
int heap[100005];
55
int sz = 0; // heap에 들어있는 원소의 수
66

7+
void print(){
8+
cout<<"PRINT:: ";
9+
for(int i=1;i<=sz;i++)
10+
cout<<heap[i]<<" ";
11+
cout<<"\n";
12+
}
13+
714
void push(int x){
815
heap[++sz] = x;
916
int idx = sz;
@@ -36,16 +43,21 @@ void pop(){
3643

3744
void test(){
3845
push(10); push(2); push(5); push(9); // {10, 2, 5, 9}
46+
print();
3947
cout << top() << '\n'; // 2
4048
pop(); // {10, 5, 9}
49+
print();
4150
pop(); // {10, 9}
51+
print();
4252
cout << top() << '\n'; // 9
4353
push(5); push(15); // {10, 9, 5, 15}
54+
print();
4455
cout << top() << '\n'; // 5
4556
pop(); // {10, 9, 15}
57+
print();
4658
cout << top() << '\n'; // 9
4759
}
4860

4961
int main(void){
5062
test();
51-
}
63+
}

‎0x17/11286.cpp renamed to ‎0x17/v11286/11286.cpp

File renamed without changes.

‎0x17/v11286/main

31.9 KB
Binary file not shown.

‎0x17/v11286/main.cc

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
#include <bits/stdc++.h>
2+
using namespace std;
3+
4+
int N;
5+
priority_queue<int, vector<int>, greater<int>> pos_pq;
6+
// min heap
7+
priority_queue<int, vector<int>, greater<int>> neg_pq;
8+
// min heap
9+
10+
int main() {
11+
ios::sync_with_stdio(false);
12+
cin.tie(NULL);
13+
14+
cin >> N;
15+
16+
for (int i = 1; i <= N; i++) {
17+
int input;
18+
cin >> input;
19+
if (input == 0) {
20+
if (!pos_pq.empty() && !neg_pq.empty()) {
21+
if (pos_pq.top() >= neg_pq.top()) {
22+
cout << -neg_pq.top() << "\n";
23+
neg_pq.pop();
24+
} else if (pos_pq.top() < neg_pq.top()) {
25+
cout << pos_pq.top() << "\n";
26+
pos_pq.pop();
27+
}
28+
} else if (!pos_pq.empty()) {
29+
cout << pos_pq.top() << "\n";
30+
pos_pq.pop();
31+
} else if (!neg_pq.empty()) {
32+
cout << -neg_pq.top() << "\n";
33+
neg_pq.pop();
34+
} else
35+
cout << 0 << "\n";
36+
} else {
37+
if (input < 0)
38+
neg_pq.push(abs(input));
39+
else
40+
pos_pq.push(input);
41+
}
42+
}
43+
}

‎0x17/v11286/sol/main

27.1 KB
Binary file not shown.

‎0x17/v11286/sol/main.cc

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
#include<bits/stdc++.h>
2+
using namespace std;
3+
4+
int N;
5+
class cmp{
6+
public:
7+
bool operator() (int a,int b){
8+
if(abs(a)==abs(b))
9+
return a>0 && b<0;
10+
else
11+
return abs(a)>abs(b);
12+
}
13+
};
14+
15+
int main(){
16+
ios::sync_with_stdio(false);
17+
cin.tie(NULL);
18+
19+
priority_queue<int, vector<int>, cmp> pq;
20+
cin>>N;
21+
22+
for(int i=1;i<=N;i++){
23+
int input;cin>>input;
24+
if(input==0){
25+
if(pq.empty())
26+
cout<<"0\n";
27+
else{
28+
cout<<pq.top()<<"\n";
29+
pq.pop();
30+
}
31+
}
32+
else
33+
pq.push(input);
34+
}
35+
}
36+
37+

0 commit comments

Comments
 (0)
0