제출 #286432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286432		egekabas	커다란 상품 (IOI17_prize)	C++14	20 / 100	185 ms	6008 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
vector<int> dp[200009];
int curval = 0;
int N;
vector<int> q(int x){
	if(dp[x].size())
		return dp[x];
	return dp[x] = ask(x);
}
vector<int> used;
int mark[200009];
int find_best(int n) {
	N = n;
	for(int i = 0; i < 470 && i < n; ++i)
		curval = max(curval, q(i)[0]+q(i)[1]);
	while(1){
		int l = 0, r = n-1;
		int lval = 0, rval = 0;
		while(l < r){
			int mid = (l+r)/2;
			while(mark[mid] && mid > l)
				--mid;
			while(mid < r && mark[mid])
				++mid;
			vector<int> cur = q(mid);
			if(cur[0] + cur[1] != curval){
				l = r = mid;
				continue;
			}
			if(cur[0]-(lower_bound(all(used), mid)-used.begin()) > 0)
				r = mid-1;
			else
				l = mid+1;
		}
		if(q(l)[0]+q(l)[1] == 0)
			return l;
		else{
			used.pb(l);
			int idx = used.size()-1;
			while(idx > 0 && used[idx-1] > used[idx]){
				swap(used[idx], used[idx-1]);
				--idx;
			}
			mark[l] = 1;
		}
	}
}

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:32:7: warning: unused variable 'lval' [-Wunused-variable]
   32 |   int lval = 0, rval = 0;
      |       ^~~~
prize.cpp:32:17: warning: unused variable 'rval' [-Wunused-variable]
   32 |   int lval = 0, rval = 0;
      |                 ^~~~

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