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

Commit ecb43e4

Browse files
author
cuberry
committed
solved 0x13 18870
1 parent b7e5043 commit ecb43e4

File tree

12 files changed

+103
-29
lines changed

12 files changed

+103
-29
lines changed

‎0x13/10816/main

40 Bytes
Binary file not shown.

‎0x13/10816/main.cc

Lines changed: 54 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,49 @@
11
#include <bits/stdc++.h>
22
using namespace std;
33

4-
#define __INPUT__
5-
#define __PRINT__
6-
#define __DEBUG__
4+
//#define __INPUT__
5+
//#define __PRINT__
6+
//#define __DEBUG__
77

88
int N, M;
99
int arr[500002];
1010

11+
int find_idx(int target, int dir){
12+
int st = 1;
13+
int en = N;
14+
int mid = (st + en) / 2;
15+
int sign=0;
16+
17+
while(st<=en){
18+
//arr[mid-1]<target
19+
if(arr[mid]==target){
20+
sign=1;
21+
if(arr[mid+dir]!=target){
22+
#ifdef __DEBUG__
23+
if(dir==-1)
24+
cout<<target<<"'s left found as "<<arr[mid+dir]<<" "<<mid<<"\n";
25+
else
26+
cout<<target<<"'s right found as "<<arr[mid+dir]<<" "<<mid<<"\n";
27+
#endif
28+
return mid;
29+
}
30+
else if(dir==-1)
31+
en=mid-1;
32+
else
33+
st=mid+1;
34+
}
35+
else if(arr[mid]<target)
36+
st=mid+1;
37+
else if(arr[mid]>target)
38+
en=mid-1;
39+
mid=(st+en)/2;
40+
}
41+
42+
return sign;
43+
}
44+
45+
46+
1147
int main() {
1248
ios::sync_with_stdio(false);
1349
cin.tie(NULL);
@@ -19,33 +55,23 @@ int main() {
1955

2056
sort(arr + 1, arr + N + 1);
2157

58+
#ifdef __INPUT__
59+
cout<<"INPUT\n";
60+
for(int i=1;i<=N;i++){
61+
cout<<arr[i]<<" ";
62+
}
63+
cout<<"\n";
64+
#endif
65+
2266
for (int i = 1; i <= M; i++) {
2367
int t;
2468
cin >> t;
25-
int st = 1;
26-
int en = N;
27-
int mid = (st + en) / 2;
28-
int ans = 0;
29-
30-
while (st <= en) {
31-
if (t == arr[mid]) {
32-
int rpos = mid;
33-
int lpos = mid - 1;
34-
while (rpos <= N && arr[rpos] == t) {
35-
ans++;
36-
rpos++;
37-
}
38-
while (lpos >= 1 && arr[lpos] == t) {
39-
ans++;
40-
lpos--;
41-
}
42-
break;
43-
} else if (t < arr[mid])
44-
en = mid - 1;
45-
else
46-
st = mid + 1;
47-
mid = (st + en) / 2;
48-
}
49-
cout << ans << " ";
69+
70+
int left=find_idx(t,-1);
71+
int right=find_idx(t,1);
72+
int sign=left;
73+
74+
cout<<right-left<<" ";
75+
5076
}
5177
}

‎0x13/18870/18870.cpp renamed to ‎0x13/v18870/18870.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,4 +21,4 @@ int main(void){
2121
}
2222
for(int i = 0; i < n; i++)
2323
cout << lower_bound(uni.begin(), uni.end(), x[i]) - uni.begin() << ' ';
24-
}
24+
}

‎0x13/18870/18870_1.cpp renamed to ‎0x13/v18870/18870_1.cpp

File renamed without changes.

‎0x13/v18870/main

46.9 KB
Binary file not shown.

‎0x13/v18870/main.cc

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
#include <bits/stdc++.h>
2+
using namespace std;
3+
4+
#define __INPUT__
5+
#define __PRINT__
6+
#define __DEBUG__
7+
8+
int N;
9+
vector<int> v;
10+
vector<int> uniq;
11+
12+
int main() {
13+
ios::sync_with_stdio(false);
14+
cin.tie(NULL);
15+
16+
cin >> N;
17+
for (int i = 1; i <= N; i++) {
18+
int input;
19+
cin >> input;
20+
v.push_back(input);
21+
}
22+
uniq = v;
23+
sort(uniq.begin(), uniq.end());
24+
uniq.erase(unique(uniq.begin(), uniq.end()),uniq.end());
25+
26+
for (auto i = 0; i < v.size(); i++) {
27+
cout << lower_bound(uniq.begin(), uniq.end(), v[i]) - uniq.begin()
28+
<< " ";
29+
}
30+
}

‎0x13/v18870/tc1

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
5
2+
2 4 -10 4 -9

‎0x13/v18870/tc2

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
6
2+
1000 999 1000 999 1000 999

‎0x13/v18870/tc3

Lines changed: 2 additions & 0 deletions
Large diffs are not rendered by default.

‎0x13/v18870/test/main

25.1 KB
Binary file not shown.

0 commit comments

Comments
 (0)
0