Submission #151691

#	Time	Username	Problem	Language	Result	Execution time	Memory
151691		gs14004	Wine Tasting (FXCUP4_wine)	C++17	100 / 100	12 ms	1024 KiB

bartender

#include "bartender.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;

namespace {
	lint encode(vector<int> v){
		lint tot = 0;
		int cnt = 0;
		for(int i=0; i<sz(v); i++){
			int rk = 0;
			for(int j=0; j<i; j++){
				if(v[j] < v[i]) rk++;
			}
			cnt++;
			tot = tot * cnt + rk;
		}
		return tot;
	}
	vector<int> decode(lint w, int n){
		vector<int> v(n);
		vector<int> lst(n);
		iota(lst.begin(), lst.end(), 1);
		for(int i=n-1; i>=0; i--){
			int md = w % (i + 1);
			w /= i + 1;
			v[i] = lst[md];
			lst.erase(lst.begin() + md);
		}
		return v;
	}
}

std::vector<int> BlendWines(int K, std::vector<int> R){
	int N = R.size();
	vector<int> tmp;
	for(int i=0; i<N; i++){
		if(R[i] > 12) tmp.push_back(R[i] - 12);
	}
	lint tot = encode(tmp);
	vector<int> ans(N);
	for(int i=0; i<N; i++){
		if(R[i] <= 12) ans[i] = 1 + (tot >> (R[i] - 1)) % 2;
	}
	tot >>= 12;
	for(int i=0; i<N; i++){
		if(R[i] > 12){
			ans[i] = 3 + (tot % 5);
			tot /= 5;
		}
	}
	return ans;
}

taster

#include "taster.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;

namespace {
	lint encode(vector<int> v){
		lint tot = 0;
		int cnt = 0;
		for(int i=0; i<sz(v); i++){
			int rk = 0;
			for(int j=0; j<i; j++){
				if(v[j] < v[i]) rk++;
			}
			cnt++;
			tot = tot * cnt + rk;
		}
		return tot;
	}
	vector<int> decode(lint w, int n){
		vector<int> v(n);
		vector<int> lst(n);
		iota(lst.begin(), lst.end(), 1);
		for(int i=n-1; i>=0; i--){
			int md = w % (i + 1);
			w /= i + 1;
			v[i] = lst[md];
			lst.erase(lst.begin() + md);
		}
		return v;
	}
}

vector<int> mis(vector<int> v){
	if(sz(v) <= 1) return v;
	vector<int> LO, HI;
	for(int i=0; i+1<sz(v); i+=2){
		if(Compare(v[i], v[i + 1]) > 0) swap(v[i], v[i + 1]);
		LO.push_back(v[i]);
		HI.push_back(v[i + 1]);
	}
	if(sz(v) & 1) LO.push_back(v.back());
	HI = mis(HI);
	auto find_match_index = [&](int x){
		int pos = find(v.begin(), v.end(), x) - v.begin();
		pos ^= 1;
		if(pos >= sz(v)) return 987654321;
		int ret = find(HI.begin(), HI.end(), v[pos]) - HI.begin();
		return ret;
	};
	sort(LO.begin(), LO.end(), [&](const int &a, const int &b){
		return find_match_index(a) < find_match_index(b);
	});
	HI.insert(HI.begin(), LO[0]); 
	LO.erase(LO.begin());
	for(auto i : {1, 0, 3, 2, 5, 4}){
		if(i >= sz(LO)) continue;
		int thres = find_match_index(LO[i]);
		thres = min(thres, sz(HI));
		int s = 0, e = thres;
		while(s != e){
			int m = (s+e)/2;
			if(Compare(HI[m], LO[i]) > 0) e = m;
			else s = m + 1;
		}
		HI.insert(HI.begin() + s, LO[i]);
	}
	return HI;
}

vector<int> get_order(vector<int> pos, int n){
	pos = mis(pos);
	vector<int> dap(n);
	for(int i=0; i<sz(pos); i++) dap[pos[i]] = i + 1;
	return dap;
}

std::vector<int> SortWines(int K, std::vector<int> A) {
	int N = sz(A);
	lint tot = 0;
	for(int i=N-1; i>=0; i--){
		if(A[i] > 2){
			tot = tot * 5 + (A[i] - 3);
		}
	}
	tot <<= 12;
	vector<int> find_ord;
	for(int i=0; i<N; i++){
		if(A[i] <= 2){
			find_ord.push_back(i);
		}
	}
	vector<int> ord = get_order(find_ord, N);
	vector<int> ans(N);
	for(int i=0; i<N; i++){
		if(A[i] <= 2){
			ans[i] = ord[i];
			if(A[i] == 2) tot += (1 << (ord[i] - 1));
		}
	}
	if(N > 12){
		auto dec = decode(tot, N - 12);
		reverse(dec.begin(), dec.end());
		for(int i=0; i<N; i++){
			if(A[i] > 2){
				ans[i] = dec.back() + 12;
				dec.pop_back();
			}
		}
	}
	return ans;
}

Compilation message (stderr)

bartender.cpp:21:14: warning: 'std::vector<int> {anonymous}::decode(lint, int)' defined but not used [-Wunused-function]
  vector<int> decode(lint w, int n){
              ^~~~~~

taster.cpp:8:7: warning: 'lint {anonymous}::encode(std::vector<int>)' defined but not used [-Wunused-function]
  lint encode(vector<int> v){
       ^~~~~~

• Subtask 1: 100 / 100