제출 #163540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163540		dolphingarlic	커다란 상품 (IOI17_prize)	C++14	0 / 100	295 ms	9728 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int find_best(int n) {
	int mx = 0, worst;
	vector<int> worst_res;
	// Finds the first lollipop
    for (worst = 0; worst < 500; worst++) {
		vector<int> res = ask(worst);
		if (res[0] + res[1] >= 22) {
			worst_res = res;
			worst++;
			break;
		} else if (res[0] + res[1] > mx) {
			mx = res[0] + res[1];
			worst_res = res;
		} else if (res[0] + res[1] == 0) return worst;
	}

	// Binary searches for the other prizes
	indexed_set remaining;
	FOR(i, worst, n) remaining.insert(i);
	while (remaining.size()) {
		int l = 0, r = remaining.size() - 1;
		while (l != r) {
			int mid = (l + r + 1) / 2;
			int pos = *remaining.find_by_order(mid);
			vector<int> res = ask(pos);
			if (res[0] + res[1] == 0) return pos;
			else if (res[0] + res[1] == worst_res[0] + worst_res[1]) {
				if (res[1] == worst_res[1]) {
					while (*remaining.begin() != pos) remaining.erase(remaining.begin());
					remaining.erase(remaining.begin());
					break;
				} else r = mid - 1;
			} else {
				remaining.erase(pos);
				break;
			}
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

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