제출 #286402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286402		egekabas	커다란 상품 (IOI17_prize)	C++14	20 / 100	3030 ms	5084 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(x < 0)
		return {0, curval};
	if(x >= N)
		return {curval, 0};
	if(dp[x].size())
		return dp[x];
	return dp[x] = ask(x);
}
int bit[200009];
void upd(int idx, int val){
	for(++idx; idx <= 200000; idx += idx&(-idx))
		bit[idx] += val;
}
int get(int idx){
	int ret = 0;
	for(++idx; idx > 0; idx -= idx&(-idx));
		ret += bit[idx];
	return ret;
}
int get(int l, int r){
	return get(r)-get(l-1);
}
	
int find_best(int n) {
	N = n;
	
	for(int i = 0; i < 600 && i < n; ++i)
		curval = max(curval, q(i)[0]+q(i)[1]);
	while(1){
		int l = 0, r = n-1;
		while(l < r){
			while(get(l, l) == -1) ++l;
			while(get(r, r) == -1) --r;
			if(l >= r) break;
			int mid = (l+r)/2;
			for(int i = 0; (mid-i) >= l || (mid+i) <= r; ++i){
				if((mid-i) >= l){
					int idx = mid-i;
					if(q(idx)[0]+q(idx)[1] == 0)
						return idx;
					if(q(idx)[0]+q(idx)[1] == curval){
						if(q(idx)[0]-q(l-1)[0]-get(l, idx) > 0){
							r = idx-1;
							break;
						}
					}
					else{
						if(get(idx, idx) != -1)
							upd(idx, -1);
					}
				}
				if((mid+i) <= r){
					int idx = mid+i;
					if(q(idx)[0]+q(idx)[1] == 0)
						return idx;
					if(q(idx)[0]+q(idx)[1] == curval){
						if(q(idx)[1]-q(r+1)[1]-get(idx, r) > 0){
							l = idx+1;
							break;
						}
					}
					else{
						if(get(idx, idx) != -1)
							upd(idx, -1);
					}
				}
			}
		}
		if(q(l)[0]+q(l)[1] == 0)
			return l;
		else
			upd(l, -1);
	}
}

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

prize.cpp: In function 'int get(int)':
prize.cpp:35:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   35 |  for(++idx; idx > 0; idx -= idx&(-idx));
      |  ^~~
prize.cpp:36:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   36 |   ret += bit[idx];
      |   ^~~

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