Submission #247371

# Submission time Handle Problem Language Result Execution time Memory
247371 2020-07-11T09:03:38 Z shenxy Wine Tasting (FXCUP4_wine) C++17
0 / 100
9 ms 796 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 (R[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_sort(vector<int> inp) {
	if (inp.size() == 1) return inp;
	vector<int> l, r, ans;
	for (int i = 0; i < inp.size() / 2; ++i) l.push_back(inp[i]);
	for (int i = inp.size() / 2; i < inp.size(); ++i) r.push_back(inp[i]);
	l = merge_sort(l), r = merge_sort(r);
	int lptr = 0, rptr = 0;
	while (lptr != l.size() || rptr != r.size()) {
		if (lptr == l.size()) ans.push_back(r[rptr++]);
		else if (rptr == r.size()) ans.push_back(l[lptr++]);
		else if (Compare(l[lptr], r[rptr]) == 1) ans.push_back(r[rptr++]);
		else ans.push_back(l[lptr++]);
	}
	return ans;
}
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_sort(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_sort(std::vector<int>)':
taster.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < inp.size() / 2; ++i) l.push_back(inp[i]);
                  ~~^~~~~~~~~~~~~~~~
taster.cpp:13:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = inp.size() / 2; i < inp.size(); ++i) r.push_back(inp[i]);
                               ~~^~~~~~~~~~~~
taster.cpp:16:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (lptr != l.size() || rptr != r.size()) {
         ~~~~~^~~~~~~~~~~
taster.cpp:16:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (lptr != l.size() || rptr != r.size()) {
                             ~~~~~^~~~~~~~~~~
taster.cpp:17:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (lptr == l.size()) ans.push_back(r[rptr++]);
       ~~~~~^~~~~~~~~~~
taster.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if (rptr == r.size()) ans.push_back(l[lptr++]);
            ~~~~~^~~~~~~~~~~
taster.cpp: In function 'std::vector<int> SortWines(int, std::vector<int>)':
taster.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); ++i) {
                  ~~^~~~~~~~~~
taster.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 13; i <= A.size(); ++i) a.insert(i);
                   ~~^~~~~~~~~~~
taster.cpp:36: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:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < rem.size(); ++i) {
                  ~~^~~~~~~~~~~~
taster.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ord.size(); ++i) ans[ord[i]] = i + 1;
                  ~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 9 ms 796 KB Correct
2 Correct 8 ms 792 KB Correct
3 Correct 9 ms 796 KB Correct
4 Correct 8 ms 780 KB Correct
5 Incorrect 9 ms 668 KB Wrong
6 Halted 0 ms 0 KB -