Submission #965750

#	Time	Username	Problem	Language	Result	Execution time	Memory
965750		Nahian9696	The Big Prize (IOI17_prize)	C++17	95.45 / 100	37 ms	4904 KiB

prize

#include "prize.h"
 
#include <bits/stdc++.h>
 
#define endl                                "\n"
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define ll                                  long long
 
using namespace std;
 
const ll max_gems = 480;
bool gems[200005];
std::vector<pair<ll,ll>> response;
 
 
 
vector<int> askk(int i) {
    if(response[i] == make_pair(-1ll, -1ll)) {
        vector<int> res = ask(i);
        response[i] = make_pair(res[0], res[1]);
        return res;
    }
 
    vector<int> res;
 
    res.push_back(response[i].first);
    res.push_back(response[i].second);
	
 
	return res;
}
 
 
int find_best(int n) {
	ll mx = 0;
	ll mxind = 0;
 
    response.resize(n+5, {-1,-1});
	priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;

 
  
	for(int i=1; i<=max_gems; i++){
		std::vector<int> v = askk(i-1);
		ll a = v[0];
		ll b = v[1];
		ll c = a+b;
		if(c==0){
			return i-1;
		}
		if(c >= mx){
			mx = c;
			mxind = i-1;
		}
	}
 
 
    for(int i=1; i<=max_gems; i++){
		std::vector<int> v = askk(i-1);
		ll a = v[0];
		ll b = v[1];
		ll c = a+b;
		if(c==0){
			return (i-1);
		} else if(c == mx) {
				pq.push({a, i-1});
			}
		if(c != mx){
			gems[i-1] = true;
		}
	}
 
  ////////////////////////////////// Thik ache /////////////////////////////////
 
 
    
 
    int cur_lolipop = max_gems, left, right;
 
    while(true) {
		// cout << cur_lolipop << " " << 79 << endl;
        vector<int> v = askk(cur_lolipop);
		ll a = v[0];
		ll b = v[1];
		ll c = a+b;
		if(c==0){
			return cur_lolipop;
		} else if(c == mx) {
				pq.push({a, cur_lolipop});
			}
 
		if(c != mx){
			gems[cur_lolipop] = true;
            cur_lolipop++;
		} else {
            left = a, right = b;
            break;
        }
    }

	

 
 
    while(right != 0) {
 
		// cout << l << " " << r << endl;
 
        int l = cur_lolipop+1, r = -1;

		while(!pq.empty()) {
			int x = pq.top().first;
			if(x <= left) {
				pq.pop();
				continue;
			}
			r = pq.top().second;
			break;
		}

		if(r == -1) r = n-1;
 
		// cout << l << " " << r << endl;
 
        while(l < r) {
 
            int mid = (l+r)/2;
			// cout << mid << " " << 105 << endl;
            vector<int> v = askk(mid);
 
            ll a = v[0];
    		ll b = v[1];
    		ll c = a+b;
 
			// cout << c << endl;
 
			if(c==0){
				return mid;
			} else if(c == mx) {
				pq.push({a, mid});
			}
 
            if(c < left + right) {
                gems[mid] == true;
                r = mid;
            } else if(a == left) {
                l = mid+1;
                for(int i = l; i <= mid; i++) {
                    response[i] = {left, right};
                }
            } else {
                r = mid - 1;
            }
 
        }
 
		vector<int> v = askk(l);
 
            ll a = v[0];
    		ll b = v[1];
    		ll c = a+b;
 
			// cout << c << endl;
 
			if(c==0){
				return l;
			} else if(c == mx) {
				pq.push({a, l});
			}
 
 
        gems[l] = true;
        cur_lolipop = l+1;
 
 
		// if(cur_lolipop==n){
		// 	return cur_lolipop;
		// }
 
        while(true) {
			// cout << cur_lolipop << " " << 134 << endl;
            vector<int> v = askk(cur_lolipop);
    		ll a = v[0];
    		ll b = v[1];
    		ll c = a+b;
			if(c==0){
				return cur_lolipop;
			} else if(c == mx) {
				pq.push({a, cur_lolipop});
			}
    		if(c != mx){
    			gems[cur_lolipop] = true;
                cur_lolipop++;
    		} else {
                left = a, right = b;
                break;
            }
        }
      
    }
 
 
 
    
    
 
    
 
 
 
 
 
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:145:27: warning: statement has no effect [-Wunused-value]
  145 |                 gems[mid] == true;
      |                 ~~~~~~~~~~^~~~~~~
prize.cpp:37:5: warning: variable 'mxind' set but not used [-Wunused-but-set-variable]
   37 |  ll mxind = 0;
      |     ^~~~~
prize.cpp:40:73: warning: control reaches end of non-void function [-Wreturn-type]
   40 |  priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
      |                                                                         ^~

• Subtask 1: 20 / 20
• Subtask 2: 75.45 / 80