#include "bartender.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
std::vector<int> BlendWines(int K, std::vector<int> a){
int N = a.size();
int G=min(N,12);
vector<int> s;
for(int i=0;i<N;++i)
if(a[i]>G)
s.pb(a[i]-G);
__int128 p=0;
//encode this shit
for(int j=0;j<s.size();++j)
{
int w=0;
for(int k=0;k<j;++k)
w+=s[k]<s[j];
p=p*(j+1)+w;
}
vector<int> o(N);
for(int i=0;i<N;++i)
{
int u=2;
if(a[i]>G) u=5;
int x=p%u; p/=u;
if(a[i]>G)
o[i]=x+3;
else o[i]=x+1;
}
assert(p==0);
return o;
}
#include "taster.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int pos[100999],N,bs[109999];
void edt(int x,int y)
{
for(;x<=N;x+=x&-x) bs[x]+=y;
}
int qry(int x)
{
int s=0;
for(;x>=1;x-=x&-x) s+=bs[x];
return s;
}
int query(int p,int q)
{
return Compare(p,q)==-1;
}
vector<int> sortr(vector<int> v)
{
if(v.size()<=1) return v;
int n=v.size();
vector<int> t;
for(int i=0;i+1<n;i+=2)
{
//v[i]<v[i+1]
if(!query(v[i],v[i+1])) swap(v[i],v[i+1]);
t.pb(v[i+1]);
}
t=sortr(t);
for(auto r:v) pos[r]=-1;
for(int i=0;i<int(t.size());++i)
pos[t[i]]=i;
N=t.size();
for(int i=1;i<=N;++i) bs[i]=0;
for(int i=2;i<=N;++i) edt(i,1);
for(int i=0;i<N;++i)
assert(qry(i+1)==i);
pos[0]=1e9;
vector<pii> vp;
for(int i=0;i<n;i+=2)
{
if(i+1<n)
vp.pb(mp(v[i],v[i+1]));
else vp.pb(mp(v[i],0));
}
sort(vp.begin(),vp.end(),[&]
(pii a,pii b) {return pos[a.se]<pos[b.se];});
int vn=vp.size();
for(int l=0,c=0,b=0,r,s;l<vn;l=r+1,b=s,++c)
{
if(c==0) s=1;
else if(c==1) s=2;
else s=(1<<c)-b;
r=min(l+s-1,vn-1);
for(int j=r;j>=l;--j)
{
pii w=vp[j]; int p;
if(!w.se) p=t.size();
else p=qry(pos[w.se]+1);
int ip;
{
int l=0,r=p;
while(l<r)
{
int m=(l+r)>>1;
if(query(t[m],w.fi)) l=m+1; else r=m;
}
ip=l;
}
t.insert(t.begin()+ip,w.fi);
{
int l=1,r=N+1;
while(l<r)
{
int m=(l+r)>>1;
if(qry(m)>=ip) r=m; else l=m+1;
}
edt(l,1);
}
}
}
return t;
}
//optimal sort end
#define pb push_back
#define SZ 666666
bool big[SZ];
int g[SZ],c[SZ];
std::vector<int> SortWines(int K, std::vector<int> o) {
srand(time(0)+19260817);
int N = o.size();
vector<int> a(N);
int G=min(N,12);
__int128 p=0;
for(int i=N-1;i>=0;--i)
{
int u,x;
if(o[i]>=3)
big[i]=1,u=5,x=o[i]-3;
else u=2,x=o[i]-1;
p=p*u+x;
}
#ifdef LOCAL
cerr<<(long long)p<<"\n";
#endif
for(int i=N-G-1;i>=0;--i)
{
g[i]=p%(i+1); p/=i+1;
}
for(int i=0;i<=N-G-1;++i)
{
c[i]=g[i];
for(int j=0;j<i;++j)
if(c[j]>=g[i]) ++c[j];
}
int oo=0;
for(int i=0;i<N;++i)
if(big[i]) a[i]=c[oo++]+G+1;
vector<int> S;
for(int i=0;i<N;++i)
if(!big[i]) S.pb(i);
random_shuffle(S.begin(),S.end());
S=sortr(S);
for(int i=0;i<S.size();++i)
a[S[i]]=i+1;
#ifdef LOCAL
for(auto t:o)
cout<<t<<",";
cout<<"\n";
for(auto t:a)
cout<<t<<",";
cout<<"\n";
#endif
return a;
}
Compilation message
bartender.cpp: In function 'std::vector<int> BlendWines(int, std::vector<int>)':
bartender.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<s.size();++j)
~^~~~~~~~~
taster.cpp: In function 'std::vector<int> SortWines(int, std::vector<int>)':
taster.cpp:135:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<S.size();++i)
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
644 KB |
Correct |
| 2 |
Correct |
9 ms |
772 KB |
Correct |
| 3 |
Correct |
9 ms |
772 KB |
Correct |
| 4 |
Correct |
10 ms |
772 KB |
Correct |
| 5 |
Correct |
10 ms |
772 KB |
Correct |
| 6 |
Correct |
9 ms |
908 KB |
Correct |
| 7 |
Correct |
9 ms |
980 KB |
Correct |
| 8 |
Correct |
8 ms |
644 KB |
Correct |
| 9 |
Incorrect |
10 ms |
908 KB |
Wrong |
| 10 |
Halted |
0 ms |
0 KB |
- |
