| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 390514 | mehrdad_sohrabi | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=2e5+100;
/*
static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;
vector<int> ask(int i) {
query_count++;
if(query_count > max_q) {
cerr << "Query limit exceeded" << endl;
exit(0);
}
if(i < 0 || i >= n) {
cerr << "Bad index: " << i << endl;
exit(0);
}
vector<int> res(2);
res[0] = rank_count[g[i] - 1][i + 1];
res[1] = rank_count[g[i] - 1][n] - res[0];
return res;
}
*/
ll val[N];
pii a[N];
ll mx=0;
pii ASK(int i){
if (val[i]==-1){
vector <int> ans=ask(i);
a[i]={ans[0],ans[1]};
val[i]=a[i].F+a[i].S;
}
return a[i];
}
ll vis[N];
void solve(ll l,ll r,ll kl,ll kr){
if (kl+kr>=mx) return ;
vector <int> cand;
for (int i=l;i<r;i++){
if (!vis[i]){
cand.pb(i);
}
}
ll s=cand.size();
s/=2;
if (cand.size()==0) return ;
if (cand.size()==1){
ASK(cand[0]);
if (val[cand[0]]<mx){
vis[cand[0]]=1;
}
return ;
}
ll mid=cand[s-1]+1;
for (int i=s;i<cand.size();i++){
ASK(cand[i]);
if (val[cand[i]]<mx){
vis[cand[i]]=1;
continue;
}
if (i!=cand.size()-1){
solve(cand[i+1],r,a[cand[i]].F,kr);
}
solve(l,mid,kl,a[cand[i]].S+i-s);
return ;
}
solve(l,mid,kl,kr+cand.size()-s);
}
int32_t find_best(int32_t n) {
memset(val,-1,sizeof val);
vector <int> rnd;
for (int i=0;i<n;i++){
rnd.pb(i);
}
random_shuffle(rnd.begin(),rnd.end());
for (int i=0;i<min(n,40);i++){
ASK(rnd[i]);
mx=max(mx,val[i]);
}
solve(0,n,0,0);
for (int i=0;i<n;i++){
if (vis[i]==1 && val[i]==0) return i;
}
return 0;
}
/*
int32_t main() {
cin >> n;
g.resize(n);
for(int i = 0; i < n; i++) {
cin >> g[i];
if(g[i] < 1) {
cerr << "Invalid rank " << g[i] << " at index " << i << endl;
exit(0);
}
}
int max_rank = *max_element(g.begin(), g.end());
rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
for(int r = 0; r <= max_rank; r++) {
for(int i = 1; i <= n; i++) {
rank_count[r][i] = rank_count[r][i - 1];
if(g[i - 1] == r)
rank_count[r][i]++;
}
}
for(int i = 0; i <= n; i++)
for(int r = 1; r <= max_rank; r++)
rank_count[r][i] += rank_count[r - 1][i];
int res = find_best(n);
cout << res << endl << "Query count: " << query_count << endl;
return 0;
}
*/
/*
8
3 2 3 1 3 3 2 3
*/