Submission #130698

#	Time	Username	Problem	Language	Result	Execution time	Memory
130698		MohamedAhmed04	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	24.13 / 100	1093 ms	88464 KiB

brunhilda

    #include <bits/stdc++.h>
    using namespace std ;
     
    const int MAX = 1e7 + 5 ;
    const int OO = 1e9 ;
     
    int dp[MAX] , freq[MAX] ;

    int main()
    {
        int n , q ;
        scanf("%d %d" , &n , &q) ;
        int arr[n] ;
        for(int i = 0 ; i < n ; ++i)
            scanf("%d" , &arr[i]) ;
        priority_queue< pair<int , int> , vector< pair<int , int> > , greater< pair<int , int> > >pq ;
        priority_queue<int , vector<int> , greater<int> >pq2 ;
        for(int i = 0 ; i < n ; ++i)
        {
            pq.push({arr[i] , arr[i]}) ;
            pq2.push(0) ;
        }
        dp[0] = 0 ;
        const int cons = 1e7 ;
        for(int i = 1 ; i <= cons ; ++i)
        {
            while(pq.size() > 0)
            {
                pair<int , int>pp = pq.top() ;
                if(pp.first == i)
                {
                    pq.pop() ;
                    pq.push({pp.first + pp.second , pp.second}) ;
                    freq[pp.first - pp.second]++ ;
                    pq2.push(pp.first) ;
                }
                else
                    break ;
            }
            while(pq2.size() > 0)
            {
                int x = pq2.top() ;
                if(freq[x])
                {
                    pq2.pop() ;
                    freq[x]-- ;
                }
                else
                    break ;
            }
            int x = pq2.top();
            if(x == i)
                dp[i] = OO ;
            else
                dp[i] = dp[x] + 1 ;
        }
        while(q--)
        {
            int x ;
            scanf("%d" , &x) ;
            if(dp[x] >= OO)
                cout<<"oo\n" ;
            else
                cout<<dp[x]<<"\n";
        }
        return 0 ;
    }

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d" , &n , &q) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d" , &arr[i]) ;
             ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d" , &x) ;
             ~~~~~^~~~~~~~~~~

• Subtask 1: 10 / 20
• Subtask 2: 5.555555555555555 / 20
• Subtask 3: 8.571428571428571 / 60