제출 #897290

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

prize

//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "prize.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
typedef pair<int, int> T;
 
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int p(int a, int b){
	return a + rng()%(b-a+1);
}
 
int find_best(int n) {
	if (n <= 5000){
		for (int i = 0; i<n; i++){
			auto x = ask(i);
			if (x[0] + x[1] == 0) return i;
		}
		assert(false);
	}
	int curr = 0;
	vector<array<int, 2>>pre(n+1, {-1, -1});
	for (int i = 0; i<100; i++){
		int r = p(1, n);
		if (pre[r][0] == -1){
			auto y = ask(r-1);
			if (y[0] + y[1] == 0) return r-1;
			pre[r][0] = y[0];
			pre[r][1] = y[1];
		}
		curr = max(curr, pre[r][0] + pre[r][1]);
	}
	vector<int>where, pref(n+1);
	vector<bool>vis(n+1);
	int left = n-curr; //powinno byc left <= 500	
	while (left--){
		where.clear();
		for (int rep = 0; rep <= n; rep++){
			if (!vis[rep]){
				where.emplace_back(rep);
			}
			if (rep) pref[rep] = pref[rep-1];
			if (vis[rep]) pref[rep]++;
		}
		int l = 1, r = (int)where.size()-1;
		int ans = -1;
		while (r >= l){
			int m = (l+r)/2;
			int pos = where[m];
			if (pre[pos][0] == -1){
				auto y = ask(pos-1);
				pre[pos][0] = y[0];
				pre[pos][1] = y[1];
			}
			auto x = pre[where[m]];
			if (x[0] + x[1] == 0) return pos-1;
			if (x[0] + x[1] < curr){
				ans = pos;
				break;
			}
			//najgorszy
			if (x[0] == pref[pos]){
				l = m+1;
			} else {
				r = m-1;
			}
		}
		// debug(ans);
		if (ans == -1) break;
		vis[ans] = 1;
		// debug(ans);
	}
	assert(false);
}

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