제출 #425685

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

prize

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef long long ll;
#ifndef wambule
#include "prize.h"
#else
int _n;
vint _x;
vint ask(int i) {
	vint dr(2);
	for(int j = 0; j < _n; ++j) {
		if(_x[j] < _x[i]) ++dr[j > i];
	}
	return dr;
}
#endif

mt19937_64 rnd(time(0));
int R(int l, int r) {
	return l + rnd() % (r - l + 1);
}

int c;
vvint cch;
set<int> s;
vint A(int i) {
	if(cch[i][0] == -1) {
		// assert(++c <= 10000);
		cch[i] = ask(i);
		s.insert(i);
	}
	return cch[i];
}

int find_best(int n) {
	cch.resize(n, vint(2, -1));
	int cm = 0;
	for(int i = 0; i < 100; ++i) {
		int x = R(0, n - 1);
		cm = max(cm, A(x)[0] + A(x)[1]);
		if(A(x)[0] + A(x)[1] == +0) return x;
	}
	for(int i = 0; i < n; ++i) {
		if(A(i)[0] + A(i)[1] == +0) return i;
		if(A(i)[0] + A(i)[1] == cm) {
			int l = i, r = n - 1;
			while(s.size()) {
				int x = *s.begin();
				if(A(x)[1] == A(i)[1]) {
					s.erase(s.begin());
					l = x;
				} else {
					r = x - 1;
					break;
				}
			}
			while(l < r) {
				int m = l + r + 1 >> 1;
				while(A(m)[0] + A(m)[1] < cm) {
					--m;
					r = m;
				}
				if(A(m)[1] == A(i)[1]) l = m;
				else r = m - 1;
			}
			i = l;
		} else if(s.size() && (*s.begin()) == i) {
			s.erase(s.begin());
		}
	}
	return 0;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	_x = {3, 2, 3, 1, 3, 3, 2, 3};
	_n = _x.size();
	cout << find_best(_n) << endl;
	return 0;
}
#endif

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~

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