Submission #292729

#	Time	Username	Problem	Language	Result	Execution time	Memory
292729		shayan_p	The Big Prize (IOI17_prize)	C++17	0 / 100	145 ms	1148 KiB

prize

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include "prize.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int n;
int dp[maxn];

bool Big(int x){
    return dp[x] >= n;
}
void go(int l, int r){
    if(r-l <= 0)
	return;
    int mid = (l+r) >> 1;
    int pos = mid;
    while(pos < r){
	vector<int> v = ask(pos);
	if(!Big(v[0] + v[1])){
	    if(v[0] + v[1] == 0)
		throw pos;
	    pos++;
	}
	else{
	    if(v[1] > 0)
		go(pos + 1, r);
	    break;
	}
    }
    pos = mid-1;
    while(pos >= l){
	vector<int> v = ask(pos);
	if(!Big(v[0] + v[1])){
	    if(v[0] + v[1] == 0)
		throw pos;
	    pos--;
	}
	else{
	    if(v[0] > 0)
		go(l, pos);
	    break;
	}
    }
}
int find_best(int n){
    dp[1] = 1;
    for(int i = 1; i < maxn; i++){
	if(1ll * i * i < maxn){
	    for(int j = i*i + 1; j < maxn; j++){
		dp[j] = max(dp[j], dp[i] + j);
	    }
	}	    
    }
    
    ::n = n;
    try{
	go(0, n);
    }
    catch(int ans){
	return ans;
    }
    assert(0);
}

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