Submission #136085

#	Time	Username	Problem	Language	Result	Execution time	Memory
136085		JustasZ	The Big Prize (IOI17_prize)	C++14	91.12 / 100	75 ms	1016 KiB

prize

    #include "prize.h"
    #include <bits/stdc++.h>
    #define pb push_back
    #define all(a) a.begin(), a.end()
    #define sz(a) (int)a.size()
    #define x first
    #define y second
    #define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
    #define rd() abs((int)rng())
    using namespace std;
    typedef long long ll;
    typedef long double ld;
    typedef pair<int, int>pii;
    const int maxn = 2e5 + 100;
    const int mod = 1e9 + 7;
    mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
    /*vector<int> ask(int i)
    {
    	cout << "? " << i << endl;
    	vector<int>a(2);
    	cin >> a[0] >> a[1];
    	return a;
    }*/
    map<int, vector<int> >mp;
    vector<int> askk(int i)
    {
    	if(!mp.count(i))
    		mp[i] = ask(i);
    	return mp[i];
    }
    int bl = 700;
    int find_best(int n)
    {
    	vector<int>a, b;
    	int mx = 0;
    	for(int i = 0; i < min(n, 500); i++)
    	{
    		a = askk(i);
    		if(a[0] + a[1] == 0)
    			return i;
    		mx = max(mx, a[0] + a[1]);
    	}
    	for(int i = 500; i < n; i += bl)
    	{
    		int j = min(i + bl - 1, n - 1);
    		int p = i;
    		a = askk(p);
    		while(a[0] + a[1] != mx)
    		{
    			if(a[0] + a[1] == 0)
    				return p;
    			p++;
    			if(p > j)
    				break;
    			a = askk(p);
    		}
    		b = askk(j);
    		while(b[0] + b[1] != mx)
    		{
    			if(b[0] + b[1] == 0)
    				return j;
    			j--;
    			if(j < p)
    				break;
    			b = askk(j);
    		}
    		if(p < j)
    		{
    			int between = b[0] - a[0];
    			if(between != 0)
    			{
    				int it = p + 1;
    				while(it < j && between > 0)
    				{
    					a = askk(it);
    					if(a[0] + a[1] != mx)
    					{
    						between--;
    						if(a[0] + a[1] == 0)
    							return it;
    					}
    					else
    					{
    						int l = it, r = j - 1;
    						while(l < r)
    						{
    							int mid = (l + r) / 2;
    							b = askk(mid);
    							if(b[0] + b[1] != mx)
    								r = mid;
    							else
    							{
    								if(b[0] > a[0])
    									r = mid - 1;
    								else
    									l = mid + 1;
    							} 
    						}
    						it = l;
    						a = askk(it);
    						--between;
    						if(a[0] + a[1] == 0)
    							return it;
    					}
    					++it;
    				}
    			}
    		}
    	}
    }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:110:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^

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