제출 #137509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137509		MAMBA	커다란 상품 (IOI17_prize)	C++17	20 / 100	114 ms	1428 KiB

prize

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

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define all(x) x.begin(),x.end()

typedef vector<int> vi;

map<int , vi> mp;
inline vi F(int i) {
	if (mp.count(i)) return mp[i];
	return mp[i] = ask(i);
}

inline int sum(vi me) {
	return accumulate(all(me) , 0);
}

int least, ans;
bitset<200000> mark;

void solve(int l , int r, int le , int ri) {
//	cout << l << ' ' << r << endl;
	if (l == r) return;
	if (le + ri == least) return;
	int mid = l + r >> 1;
	bool happy = false;
	rep(i , 0 , r - l) {
		if (i & 1) mid -= i;
		else mid += i;
		vi me = F(mid);
		mark[mid] = true;
		if (sum(me) == 0) ans = mid;
		if (sum(me) == least) {
			happy = true;
			break;
		}
	}

	if (!happy) return;

	int ptr = l;
	while (!mark[ptr]) ptr++;
	int ptr2 = ptr;
	while (sum(F(ptr2)) != least) ptr2++;

	solve(l , ptr , le , ptr2 - ptr + F(ptr2)[1]);

	ptr = r - 1;
	while (!mark[ptr]) ptr--;
	ptr2 = ptr;
	while (sum(F(ptr2)) != least) ptr2--;

	solve(ptr + 1 , r , ptr - ptr2 + F(ptr2)[0], ri);

}

int find_best(int n) {
	mp.clear();
	
	rep(i , 0 , n) mark[i] = false;

	least = -1;
	for (int i = 1; i * i < n; i++) 
		least = max(least , sum(F(i)));

//	cout << least << endl;

	solve(0 , n , 0 , 0);

	return ans;
}

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

prize.cpp: In function 'void solve(int, int, int, int)':
prize.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~

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