제출 #982752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982752		Lalic	커다란 상품 (IOI17_prize)	C++17	100 / 100	28 ms	4704 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int bit[MAXN];

void add(int pos, int x, int n){ for(;pos<=n;pos+=(pos&-pos)) bit[pos]+=x; }
int get(int pos){
	int ret=0;
	for(;pos>0;pos-=(pos&-pos)) ret+=bit[pos];
	return ret;
}

pii memo[MAXN];

pii query(int x){
	if(memo[x].fi!=-1) return memo[x];
	vector<int> temp=ask(x);
	return memo[x]={temp[0], temp[1]};
}

int mark[MAXN], tot;

int getNext(int l, int r, int comp, int n){
	if(r<l) return -1;
	
	int curr=(l+r)>>1;
	pii at=query(curr);
	
	if(!mark[curr] && at.fi+at.se<comp){
		mark[curr]=1;
		add(curr+1, 1, n);
		return curr;
	}
	
	if(at.fi+at.se==comp){
		if(at.se>get(n)-get(curr+1)) return getNext(curr+1, r, comp, n);
		return getNext(l, curr-1, comp, n);
	}
	
	int temp=getNext(curr+1, r, comp, n);
	if(temp!=-1) return temp;
	return getNext(l, curr-1, comp, n);
}

int find_best(int n){
	for(int i=0;i<n;i++) memo[i]={-1, -1};
	
	int ver=-1, val=-1;
	
	for(int i=0;i<8;i++){
		int curr=rng()%n;
		pii at=query(curr);
		if(at.fi+at.se>val){
			val=at.fi+at.se;
			ver=curr;
		}
	}
	
	for(int i=0;i<query(ver).se;i++){
		int curr=getNext(ver+1, n-1, val, n);
		tot++;
		
		if(curr==-1) break;
		
		pii aux=query(curr);
		if(aux.fi+aux.se==0)
			return curr;
	}
	
	tot=query(ver).se;
	
	for(int i=0;i<query(ver).fi;i++){
		int curr=getNext(0, ver-1, val, n);
		tot++;
		
		if(curr==-1) break;
		
		pii aux=query(curr);
		if(aux.fi+aux.se==0)
			return curr;
	}
	
	return -1;
}

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