답안 #247343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247343 2020-07-11T08:51:56 Z shenxy 포도주 시음 (FXCUP4_wine) C++17
0 / 100
8 ms 892 KB
#include "bartender.h"
#include <algorithm>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
vector<int> BlendWines(int K, vector<int> R){
	vector<int> ans(R.size(), 0), f12, rem;
	__int128_t x = 0, fac[R.size()];
	for (int i = 0; i < R.size(); ++i) {
		if (i <= 12) f12.push_back(i);
		else rem.push_back(i);
	}
	os a;
	for (int i = 13; i <= R.size(); ++i) a.insert(i);
	fac[0] = 1;
	for (int i = 1; i < R.size(); ++i) fac[i] = i * fac[i - 1];
	for (int i = 0; i < rem.size(); ++i) {
		x = x + a.order_of_key(R[rem[i]]) * fac[rem.size() - i - 1];
		a.erase(R[rem[i]]);
	}
	for (int i = 0; i < f12.size(); ++i) {
		ans[f12[i]] = x % 3 + 1;
		x /= 3;
	}
	for (int i = 0; i < rem.size(); ++i) {
		ans[rem[i]] = x % 4 + 4;
		x /= 4;
	}
	return ans;
}
#include "taster.h"
#include <algorithm>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
vector<int> merge_insertion(vector<int> a) {
	if (a.size() == 1) return a;
	bool yay[a.size()];
	fill_n(yay, a.size(), false);
	for (int i = 1; i < a.size(); i += 2) {
		if (Compare(a[i - 1], a[i]) == 1) yay[i - 1] = true;
		else yay[i] = true;
	}
	vector<int> g, s, funn;
	for (int i = 0; i < a.size(); ++i) {
		if (yay[i]) g.push_back(a[i]);
	}
	g = merge_insertion(g);
	for (int i = 0; i < a.size(); ++i) {
		if (g.front() == a[i]) {
			if (i % 2) g.insert(g.begin(), a[i - 1]);
			else g.insert(g.begin(), a[i + 1]);
			break;
		}
	}
	for (int i = 2; i < g.size(); ++i) {
		for (int j = 0; j < a.size(); ++j) {
			if (g[i] == a[j]) {
				if (i % 2) s.push_back(a[i - 1]);
				else s.push_back(a[i + 1]);
				break;
			}
		}
	}
	if (a.size() % 2) s.push_back(a[a.size() - 1]);
	if (s.size() >= 2) swap(s[0], s[1]), funn.push_back(3), funn.push_back(2);
	else if (s.size() == 1) funn.push_back(2);
	if (s.size() >= 4) swap(s[2], s[3]), funn.push_back(5), funn.push_back(4);
	else if (s.size() == 3) funn.push_back(4);
	if (s.size() > 4) {
		reverse(s.begin() + 4, s.end());
		for (int i = s.size() + 1; i > 5; --i)funn.push_back(i);
	}
	if (a.size() % 2) {
		for (int i = 0; i < s.size(); ++i) {
			if (a[a.size() - 1] == s[i]) {
				funn[i] = g.size();
				break;
			}
		}
	}
	for (int i = 0; i < s.size(); ++i) {
		int l = 0, u = funn[i], m;
		while (l != u) {
			m = (l + u) / 2;
			if (Compare(s[i], g[m]) == 1) l = m + 1;
			else u = m;
		}
		for (int j = 0; j < s.size(); ++j) {
			if (funn[j] > l) ++funn[j];
		}
		g.insert(g.begin() + l, s[i]);
	}
	return g;
}
vector<int> SortWines(int K, vector<int> A) {
	vector<int> ans(A.size(), 0), f12, rem;
	__int128_t x = 0, fac[A.size()];
	for (int i = 0; i < A.size(); ++i) {
		if (A[i] < 4) f12.push_back(i);
		else rem.push_back(i);
	}
	for (int i = rem.size() - 1; i >= 0; --i) x = x * 4 + A[rem[i]] - 4;
	for (int i = f12.size() - 1; i >= 0; --i) x = x * 3 + A[f12[i]] - 1;
	os a;
	for (int i = 13; i <= A.size(); ++i) a.insert(i);
	fac[0] = 1;
	for (int i = 1; i < A.size(); ++i) fac[i] = i * fac[i - 1];
	for (int i = 0; i < rem.size(); ++i) {
		ans[rem[i]] = *a.find_by_order(x / fac[rem.size() - 1 - i]);
		x %= fac[rem.size() - 1 - i];
		a.erase(ans[rem[i]]);
	}
	vector<int> ord = merge_insertion(f12);
	for (int i = 0; i < ord.size(); ++i) ans[ord[i]] = i + 1;
	return ans;
}

Compilation message

bartender.cpp: In function 'std::vector<int> BlendWines(int, std::vector<int>)':
bartender.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < R.size(); ++i) {
                  ~~^~~~~~~~~~
bartender.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 13; i <= R.size(); ++i) a.insert(i);
                   ~~^~~~~~~~~~~
bartender.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < R.size(); ++i) fac[i] = i * fac[i - 1];
                  ~~^~~~~~~~~~
bartender.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < rem.size(); ++i) {
                  ~~^~~~~~~~~~~~
bartender.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < f12.size(); ++i) {
                  ~~^~~~~~~~~~~~
bartender.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < rem.size(); ++i) {
                  ~~^~~~~~~~~~~~

taster.cpp: In function 'std::vector<int> merge_insertion(std::vector<int>)':
taster.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < a.size(); i += 2) {
                  ~~^~~~~~~~~~
taster.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i) {
                  ~~^~~~~~~~~~
taster.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i) {
                  ~~^~~~~~~~~~
taster.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 2; i < g.size(); ++i) {
                  ~~^~~~~~~~~~
taster.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a.size(); ++j) {
                   ~~^~~~~~~~~~
taster.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); ++i) {
                   ~~^~~~~~~~~~
taster.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); ++i) {
                  ~~^~~~~~~~~~
taster.cpp:62:21: 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:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); ++i) {
                  ~~^~~~~~~~~~
taster.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 13; i <= A.size(); ++i) a.insert(i);
                   ~~^~~~~~~~~~~
taster.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < A.size(); ++i) fac[i] = i * fac[i - 1];
                  ~~^~~~~~~~~~
taster.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < rem.size(); ++i) {
                  ~~^~~~~~~~~~~~
taster.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ord.size(); ++i) ans[ord[i]] = i + 1;
                  ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 892 KB Correct
2 Correct 8 ms 796 KB Correct
3 Correct 8 ms 672 KB Correct
4 Incorrect 8 ms 704 KB Wrong
5 Halted 0 ms 0 KB -