Submission #150903

#	Time	Username	Problem	Language	Result	Execution time	Memory
150903		fjzzq2002	Wine Tasting (FXCUP4_wine)	C++17	100 / 100	11 ms	1080 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
map<pii,int> sb;
int query(int p,int q)
{
	if(p>q) return !query(q,p);
	if(sb.count(pii(p,q)))
		return sb[pii(p,q)];
	return sb[pii(p,q)]=(Compare(p,q)==-1);
}

void sort(std::vector<int> &v) {
    if (v.size() == 1)
        return;
    std::vector<int> t;
    std::map<int, int> m;
    for (size_t i = 1; i < v.size(); i += 2) {
        if (!query(v[i - 1], v[i]))
            std::swap(v[i - 1], v[i]);
        t.push_back(v[i]), m[v[i]] = v[i - 1];
    }
    sort(t);
    int ex = v.size() & 1 ? v.back() : -1;
    v = t;
    v.insert(v.begin(), m[t[0]]);
    for (size_t p = 4, l = 1, r = 3; l < t.size(); p <<= 1, l = r, r = p - r)
        for (size_t i = std::min(r, t.size()) - 1, j = std::min(p, v.size()) - 1; i >= l; --i) {
            while (v[j] != t[i]) --j;
            v.insert(std::lower_bound(v.begin(), v.begin() + j, m[t[i]], query), m[t[i]]);
        }
    if (ex != -1)
        v.insert(std::lower_bound(v.begin(), v.end(), ex, query), ex);
}

//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(123111111+__TIME__[7]*10000+__TIME__[6]*100
	+__TIME__[5]*11231+__TIME__[4]*1231+__TIME__[3]*123132
	+__TIME__[2]*12111+__TIME__[1]*11111+time(0));
	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());
	sort(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:87:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<S.size();++i)
              ~^~~~~~~~~

• Subtask 1: 100 / 100