moaz123's blog

help test case 6
By moaz123, 9 years ago, In English

problem :: C. Vasya and Basketball link :: http://codeforces.com/problemset/problem/493/C

i tried to change my code over and over again but same result (wrong answer at test case 6) i don't know why ? can someone give me a hint or something .

that's my code . thanks !

include

include <stdio.h>

include

include <string.h>

include

include

include

include

include

include <math.h>

using namespace std;

long int T1,T2; vectorarr1; set a;

bool binarysearch(long int s) { long int mid,high=T1,low=0; while(high>low+1) { mid=(high+low)/2;

if(arr1[mid]==s)
        return true;

    if(arr1[mid]<s)
        low=mid -1;

    else
        high = mid +1;
}
return false;

}

int main() {

cin>>T1;
long int q;
for(long int i=0; i<T1; i++)
{
    cin>>q;
    arr1.push_back(q);
    a.insert(q);
}
sort(arr1.begin(),arr1.end());

cin>>T2;

for(long int i=0; i<T2; i++)
{
    cin>>q;
    a.insert(q);
}


long int r1=0,r2=0,ans1=0,ans2=0;
for( set<long int>::iterator i=a.begin(); i!=a.end(); i++)
{
    if(binary_search(arr1.begin(),arr1.end(),*i))
        r1++;

    else
        r2++;

    if(r2>r1)
    {
        ans1+=r1*2;
        ans2+=r2*2;
        r1=0;
        r2=0;
    }

}
cout<<ans1+(r1*3)<<":"<<ans2+(r2*3)<<endl;
return 0;

}

really sorry if i wasn't clear enough !!

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

Advices for you if you need to write a blog again !!

1- If you need help with a wrong answer verdict after you completely unable to solve the problem share your submission with us via clicking in the tool bar, select Submission and put your submission id.

2- If you need to share a code with us you can use then click on Block and paste your code there. :)

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Where is the problem statement ?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did it quite differently. Add the positions of both players to two vectors and sort them. Then try every possible value of d (you only need to consider existing positions and 0) using a two pointers method (one on each vector) to know how many 2-point throws each player has.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    LOL i think my code is wrong i just realized that now . man greedy is the worst :D !! . from now on greedy is the last algorithm that i am gonna think to solve the problem with . so i will code your solution so thanks !! :D

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the number is 10 ^ 5 and and the vector is 10 ^ 5 that means n ^ 2 and n is 10 ^ 5 time limit !!

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I think you're not understanding the two-pointers method. In the case of this problem, the idea is to have two variables indicating the current position of the "pointers" on each vector. While the current value of d is greater or equal than the element at the position of the cursor, you move the cursor forward and it stays there, you don't need to start all over from the beginning every iteration.

      So, if the vectors are sorted in non-decreasing order and the cursor is at position "i" (0-indexed) (the first position bigger than d), the player scores (i) 2-point throws and (N - i) 3-point throws.

      → Reply