| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 90001 | nikolapesic2802 | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
os << '{';
for(int i=0;i<sz(a);i++)
{
if(i>0&&i<sz(a)-1)
os << ", ";
os << a[i];
}
os << '}';
return os;
}
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;
}
/*
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
*/
int N;
struct segTree{
vector<double> lazy;
vector<double> maxx;
vector<int> num;
void prop(int i)
{
if(lazy[i]==1)
return;
lazy[2*i]*=lazy[i];
lazy[2*i+1]*=lazy[i];
maxx[2*i]*=lazy[i];
maxx[2*i+1]*=lazy[i];
lazy[i]=1;
}
void update(int i)
{
if(maxx[2*i]>maxx[2*i+1])
{
maxx[i]=maxx[2*i];
num[i]=num[2*i];
}
if(maxx[2*i]<maxx[2*i+1])
{
maxx[i]=maxx[2*i+1];
num[i]=num[2*i+1];
}
if(maxx[2*i]==maxx[2*i+1])
{
maxx[i]=maxx[2*i];
num[i]=num[2*i]+num[2*i+1];
}
}
void init(int l=0,int r=N-1,int i=0)
{
lazy[i]=1;
if(l==r){
maxx[i]=1,num[i]=1;
return;
}
int m=(l+r)>>1;
init(l,m,2*i);
init(m+1,r,2*i+1);
update(i);
}
void initi()
{
lazy.resize(4*N);
maxx.resize(4*N);
num.resize(4*N);
init();
}
void add(int qs,int qe,double what,int l=0,int r=n-1,int i=1)
{
if(qs>r||qe>l)
return;
if(qs<=l&&qe>=r)
{
lazy[i]*=what;
maxx[i]*=what;
return;
}
prop(i);
int m=(l+r)>>1;
add(qs,qe,what,l,m,2*i);
add(qs,qe,what,m+1,r,2*i+1);
update(i);
}
int get_random_pos(int l=0,int r=n-1,int i=1)
{
//printf("%i %i %i\n",l,r,i);
if(l==r)
return l;
prop(i);
int m=(l+r)>>1;
if(maxx[2*i]==maxx[2*i+1])
{
//printf("ISTO! %i\n",m);
int d=r-l+1,num1=num[2*i],num2=num[2*i+1];
double s1=(double)num1/d,s2=(double)num2/d;
double s=s1+s2;
double lim=(double)s1/s;
double ra=(double)rand()/RAND_MAX;
if(ra<=lim)
return get_random_pos(l,m,2*i);
else
return get_random_pos(m+1,r,2*i+1);
}
else
{
if(maxx[2*i]>maxx[2*i+1])
return get_random_pos(l,m,2*i);
else
return get_random_pos(m+1,r,2*i+1);
}
}
};
int find_best(int n) {
N=n;
segTree tree;
tree.initi();
while(true)
{
//printf("1\n");
int pos=tree.get_random_pos();
//printf("2\n");
vector<int> tr=ask(pos);
int t=tr[0]+tr[1];
if(t==0)
return pos;
tree.add(pos,pos,0);
tree.add(0,pos-1,(double)tr[0]/t);
tree.add(pos+1,n-1,(double)tr[1]/t);
}
}
int 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;
}