제출 #78409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78409		shoemakerjo	커다란 상품 (IOI17_prize)	C++14	97.44 / 100	39 ms	2384 KiB

prize

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

using namespace std;
#define pii pair<int, int>
#define mp make_pair

#define maxn 200010
int blk;
int qs[maxn][2];
int numqueries = 0;

pii query(int spot) {
	if (qs[spot][0] != -1) 
		return pii(qs[spot][0], qs[spot][1]);
	numqueries++;
	assert(numqueries <= 10000); //induce run time error instead of WA
	//seems that above got hit
	vector<int> res = ask(spot);
	qs[spot][0] = res[0];
	qs[spot][1] = res[1];
	return pii(res[0], res[1]);
}

queue<pair<pii, pii>> q;

int find_best(int n) {
	//we don't really care  what happens for smaller n,
	//   b/c it is not a function of n
	for (int i = 0; i < n; i++) {
		qs[i][0] = qs[i][1] = -1;
	}

	//i am a little worried about exact blk bound
	blk = sqrt(n)+50; //changed from 5 to 50
	blk = min(blk, n); //just making sure

	int bigskip = n+1;
	int smallskip = -1;

	int mxind = -1;
	int mxstuff = -1;
	for(int i = 0; i < blk; i++) {
		pii res = query(i);
		if(res.first + res.second == 0)
			return i; //this will always be there
		if (res.first == 0) {
			//none smaller on left
			smallskip = max(smallskip, i);
		}
		if (res.second == 0) {
			bigskip = min(bigskip, i);
		}
		if (res.first+ res.second >= mxstuff) {
			mxstuff = res.first + res.second;
			mxind = i;
		}
	}
	int aft = query(mxind).second;
	int numtot = mxstuff; //total number less than biggest guy
	int nc = 0;
	for (int i = 0; i < blk; i++) {
		pii cur = query(i);
		if (cur.first + cur.second != numtot) nc++;
	}




	q.push(mp(mp(blk, n-1), mp(nc, 0))); 
		//gives number to left & right of range

	while (q.size()) {
		auto cur = q.front(); q.pop();
		int cleft = cur.first.first;
		int cright = cur.first.second;

		if (cright <= smallskip) continue;
		if (cleft >= bigskip) continue;

		if (cleft > cright) continue; //why would we care
		int numtoleft = cur.second.first;
		int numtoright = cur.second.second;

		if (numtoleft + numtoright == numtot) continue; //why bother
		if (cleft == cright) {
			pii cur = query(cleft);
			if (cur.first + cur.second == 0) return cleft;
			continue;
		}

		bool done = false;
		int mid = (cleft + cright)/2;
		int omid = mid;
		int tookout = 0;
		while (mid != cright+1) {
			pii cur = query(mid);

			if (cur.first == 0) {
				smallskip = max(smallskip, mid);
			}
			if (cur.second == 0) {
				bigskip = min(bigskip, mid);
			}
			if (cur.first + cur.second == numtot) {
				q.push(mp(mp(cleft, omid-1), 
					mp(numtoleft, cur.second + tookout)));
				q.push(mp(mp(mid+1, cright), 
					 mp(cur.first, numtoright)));
				done = true;
				break;
			}
			else {

				tookout++;
				if (cur.first + cur.second == 0) return mid;
				mid++;
			}
		}
		if (done) continue;
		mid = omid-1;
		while (mid != cleft-1) {
			pii cur = query(mid);
			if (cur.first == 0) {
				smallskip = max(smallskip, mid);
			}
			if (cur.second == 0) {
				bigskip = min(bigskip, mid);
			}
			if (cur.first + cur.second == numtot) {
				q.push(mp(mp(cleft , mid-1), 
					mp(numtoleft, cur.second)));
				done = true;
				break;
			}
			else {
				if (cur.first + cur.second == 0) return mid;
				mid--;
			}
		}
		
	}

	return 0;
}
//at most sqrt(n) guys that are not the maximums
//if we query smth not the maximum, we split it in half
//grader can behave adversarily

//need to cut out 256 of them
//idea could be to cut out from first section
// (just go forward until we know we got it)

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:59:6: warning: unused variable 'aft' [-Wunused-variable]
  int aft = query(mxind).second;
      ^~~

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