oj.uz

Submission #420972

# Submission time Handle Problem Language Result Execution time Memory
420972 2021-06-08T15:39:37 Z daanolav The Big Prize (IOI17_prize) C++14
20 / 100
 117 ms 288 KB 
#include "prize.h"
#include <tuple>
#include <queue>

using namespace std;

typedef tuple<float,int,int> fii;

int n,s,e,mid;
float amount;
std::vector<int> res;


int find_best(int n) {

    ::n = n;
	// std::vector<int> res = ask(i);
	priority_queue<fii,vector<fii>,less<fii>> q;

	res = ask(n / 2);

	if(res[0] + res[1] == 0) {
        return n / 2;
	}

	q.push({(float) res[0] / (float) (n / 2),0, n / 2 - 1});
	q.push({(float) res[1] / (float) (n - n / 2 - 1),n / 2 + 1,n - 1});

	while(!q.empty()) {
        tie(amount,s,e) = q.top();
        q.pop();

        if(s > e) {
            continue;
        }

        mid = (e + s) / 2;
        res = ask(mid);
        if(res[0] + res[1] == 0) {
            return mid;
        }

        q.push({(float) res[0] / (float) (mid - s),s,mid - 1});
        q.push({(float) res[1] / (float) (e - mid),mid + 1,e});



	}


	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 0 ms 200 KB Output is correct
6 Correct 1 ms 280 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 0 ms 284 KB Output is correct
9 Correct 1 ms 280 KB Output is correct
10 Correct 1 ms 200 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 0 ms 200 KB Output is correct
6 Correct 1 ms 284 KB Output is correct
7 Correct 0 ms 288 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Incorrect 117 ms 200 KB Incorrect
12 Halted 0 ms 0 KB -