Submission #150402

#	Time	Username	Problem	Language	Result	Execution time	Memory
150402		还没编好 (#200)	Wine Tasting (FXCUP4_wine)	C++17	5 / 100	13 ms	1024 KiB

bartender

#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;
}

taster

#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)[phone]);
	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 (stderr)

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)
              ~^~~~~~~~~

• Subtask 1: 5 / 100