제출 #245518

#제출 시각아이디문제언어결과실행 시간메모리
245518LittleFlowers__커다란 상품 (IOI17_prize)C++17
20 / 100
58 ms5264 KiB
#include <bits/stdc++.h> using namespace std; #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;}) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rng(1012); int rnd(int l,int r){return l+rng()%(r-l+1);} #define fasty ios_base::sync_with_stdio(0),cin.tie(0); #define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a) #define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a) #define forv(a,b) for(auto&a:b) #define fi first #define se second #define pb push_back #define ii pair<int,int> #define mt make_tuple #define all(a) a.begin(),a.end() #define reset(f, x) memset(f, x, sizeof(f)) #define gg exit(0); #ifndef UNX #include "prize.h" #endif // UNX const int N=200010; int asked; vector<int> dd[N]; int nn; #ifdef UNX int arr[N]; vector<int> ask(int p){ asked++; int x=0, y=0; forinc(i,1,p) x+=arr[i]<arr[p+1]; forinc(i,p+2,nn) y+=arr[i]<arr[p+1]; return {x,y}; } #endif // UNX vector<int> qry(int i){ return dd[i].size() ? dd[i] : dd[i]=ask(i-1); } int small; int same(int i,int j){ auto x=qry(j); return x[0]+x[1]==small; } int cnt(int i,int j){ if(i>j) swap(i,j); auto x=qry(i), y=qry(j); return y[0]-x[0]-(x[0]+x[1]>y[0]+y[1]); } int find_best(int n){ nn=n; int l=1; auto a=qry(1); if(a[0]+a[1]==0) return 0; small=a[0]+a[1]; int i=l, sz=0; vector<int> val; vector<int> lf(555),rt(555); forinc(i,0,500){ lf[i]=1; rt[i]=n; } int cur=0; while(i<n){ int le=max(i+1,lf[cur]),mi,ri=rt[cur]; cur++; int skip=0; while(le<=ri){ mi=(le+ri)/2; auto a=qry(mi); if(a[0]+a[1]>small){ small=a[0]+a[1]; l=i=mi; skip=1; sz=0; forinc(t,0,500){ lf[t]=1; rt[t]=n; } break; } if(same(l,mi)){ forinc(j,cnt(l,mi),500) lf[j]=max(lf[j],mi); forinc(j,cur,cnt(l,mi)-1) rt[j]=min(rt[j],mi); } if(same(l,mi) && cnt(l,mi)==sz) i=mi,le=mi+1; else ri=mi-1; } if(i==n) break; if(skip){ continue; } auto a=qry(++i); if(a[0]+a[1]==0) return i-1; sz++; } } #ifdef UNX main(){ #define task "TASK" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); //freopen(task".out","w",stdout); } int n=in; int answ; forinc(i,1,n) if((arr[i]=in)==1) answ=i; cout<<find_best(n)<<"\n"; cerr<<answ-1<<"\n"; cerr<<asked<<"\n"; } #endif // UNX

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:104:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...