Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct Word{
- int ogord;
- string va;
- Word(){};
- Word(int ogord1, string va1){
- ogord = ogord1;
- va = va1;
- };
- };
- int W, N;
- Word pos[1000000];
- int cal_search(int k, string q){
- int l = 0;
- int r = W-1;
- int omid = 0;
- int okay = -1; //Okay declared outside of loop.
- // If the value is okay, the okay will equal the
- // mid or the position of the string.
- while(l<=r){
- int mid = (l+r)/2; //mid has to be inside of the loop,
- // because the answer should be the value of okay, not the mid.
- if(omid == mid){
- break;
- }
- string posval = pos[mid].va;
- if(q == posval.substr(0, q.size())){
- okay = mid;
- }
- if(q == posval){ //If q (the value we are testing) is the same as the pos value,
- // then we do not have to loop any further.
- break;
- }else if(q < posval){ //If q(the value we are testing) is less than the pos value,
- // it means that the current mid value is more than the q, which means that we have
- // to move the r (the largest value) to the mid to make the range include smaller numbers.
- r = mid;
- }else{ //If q(the value we are testing) is more than the pos value,
- // it means that the current mid value is less than the q, which means that we have
- // to move the l (the smalles value) to the mid to make the range include bigger numbers.
- l = mid;
- }
- omid = mid; //omid should be declared at the end of the loop.
- // The old-mid will be the old value of the mid when being compared
- // to the current mid in the next loop.
- }
- int ans = -1;
- if(okay>=0){
- Word b = pos[okay+k-1];
- if(q == b.va.substr(0, q.size())){
- ans = b.ogord;
- }
- }
- // if(q == pos[ans].va.substr(0, q.size())) ans = okay + k-1;
- return ans;
- }
- int main(){
- //ios_base::sync_with_stdio(0), cin.tie(0);
- //freopen( "auto/1.in", "r", stdin);
- freopen("auto.in", "r", stdin);
- freopen("auto.out", "w", stdout);
- cin >> W >> N;
- string va;
- for(int i=0; i<W; i++){
- cin >> va;
- pos[i] = Word(i+1, va);
- }
- sort(pos, pos+W
- , [](const Word& a, const Word& b){
- return a.va < b.va;
- }
- );
- // for(int i=0; i<W; i++){
- // Word a = pos[i];
- // cout << a.va << ", pos: " << a.ogord << '\n';
- // }
- for(int i=0; i<N; i++){
- int vaa;
- string vab;
- cin >> vaa >> vab;
- int ans = cal_search(vaa, vab);
- cout << ans << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
