oj.uz

답안 #150845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150845 2019-09-01T08:59:13 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) 포도주 시음 (FXCUP4_wine) C++17
0 / 100
 1000 ms 1032 KB 
#include "bartender.h"

std::vector<int> BlendWines(int K, std::vector<int> R){
	int N = R.size();
	std::vector<int> a(N,1), b(N);

	for (int i = 0; i < N; i++){
		b[i] = 7 - i % 7;
	}
	b.back() = 8;
	for (int i = 0; i < N; i++) a[i] = b[R[i] - 1];

	return a;
}

#include "taster.h"
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int n = 5;
map<vector<int>, int> chk;
map<vector<int>, pair<int, int> > wow;
int c[6][6]; pair<int, int> h[36];

int minComp(vector<int> choose)
{
	sort(choose.begin(), choose.end());
	if (chk.count( choose )) return chk[choose ];
	int& r = chk[choose];

	int s[6], e[6];
	for (int k = 0; k < n; k++){
		s[k] = h[choose[k]].first;
		e[k] = h[choose[k]].second;
	}

	int p[6];
	for (int k = 0; k < n; k++){
		p[k] = k;
	}

	int u = 0;
	do{
		int c = 0;
		int v[6];
		if (c == 0) for (int k = 0; k < n; k++){
			if (s[k] <= p[k] && p[k] <= e[k]) c++;
			else break;
		}
		if (c == n) ++u;
	} while (next_permutation(p, p + n));

	if (u == 0) r = 1000;
	else if (u == 1) r = 0;
	else{
		auto& w = wow[choose];
		r = 1000;
		for (int k = 0; k < n; k++){
			int last = choose[k];
			for (int p = s[k]; p < e[k]; p++){
				int u = c[p + 1][e[k]];
				int v = c[s[k]][p];
				choose[k] = u; int a = minComp(choose) + 1;
				choose[k] = v; int b = minComp(choose) + 1;
				if (r > max(a, b)){
					r = max(a, b);
					w = { last, p };
				}
			}
			choose[k] = last;
		}
	}
	return r;
}

std::vector<int> SortWines(int K, std::vector<int> A) {
	for (int i = 0, u = 0; i < 6; i++){
		for (int j = i; j < 6; j++){
			c[i][j] = u;
			h[u] = { i,j };
			u++;
		}
	}

	int N = A.size();
	
	vector<int> b(N);
	for (int i = 0; i < N; i++) b[i] = 7 - i % 7;
	b.back() = 8;
	vector<int> pos[10];
	for (int i = 0; i < N; i++) pos[b[i]].push_back(i);

	vector<int> P(N);

	vector<int> one;
	for (int i = 0; i < N; i++) if (A[i] == 1) one.push_back(i);

	if (one.size() == 1){
		P[one[0]] = pos[1][0];
	}
	if (one.size() == 2){
		if (Compare(one[0], one[1]) == -1){
			P[one[0]] = pos[1][0];
			P[one[1]] = pos[1][1];
		}
		else{
			P[one[0]] = pos[1][1];
			P[one[1]] = pos[1][0];
		}
	}
	if (one.size() == 3){
		if (Compare(one[0], one[1]) == -1){
			if (Compare(one[1], one[2]) == -1){
				P[one[0]] = pos[1][0];
				P[one[1]] = pos[1][1];
				P[one[2]] = pos[1][2];
			}
			else{
				if (Compare(one[0], one[2]) == -1){
					P[one[0]] = pos[1][0];
					P[one[1]] = pos[1][2];
					P[one[2]] = pos[1][1];
				}
				else{
					P[one[0]] = pos[1][2];
					P[one[1]] = pos[1][0];
					P[one[2]] = pos[1][1];
				}
			}
		}
		else{
			if (Compare(one[2], one[1]) == -1){
				P[one[0]] = pos[1][2];
				P[one[1]] = pos[1][1];
				P[one[2]] = pos[1][0];
			}
			else{
				if (Compare(one[0], one[2]) == -1){
					P[one[0]] = pos[1][1];
					P[one[1]] = pos[1][0];
					P[one[2]] = pos[1][2];
				}
				else{
					P[one[0]] = pos[1][1];
					P[one[1]] = pos[1][2];
					P[one[2]] = pos[1][0];
				}
			}
		}
	}
	sort(one.begin(), one.end(), [&](const int& a, const int& b){return P[a] < P[b]; });

	for (int k = 2; k <= 8; k++){
		vector<int> alc;
		for (int i = 0; i < N; i++) if (A[i] == k) alc.push_back(i);

		if (alc.empty()) continue;

		if (alc.size() == 1){
			P[alc[0]] = pos[k][0];
		}
		if (alc.size() == 2){
			if (Compare(alc[0], one[0]) == -1){
				P[alc[0]] = pos[k][0];
				P[alc[1]] = pos[k][1];
			}
			else{
				P[alc[0]] = pos[k][1];
				P[alc[1]] = pos[k][0];
			}
		}
		if (alc.size() >= 3){
			n = alc.size();
			vector<int> choose(n, c[0][n - 1]);
			int u = minComp(choose);
			while (1){
				int s[6], e[6];
				for (int k = 0; k < n; k++){
					s[k] = h[choose[k]].first;
					e[k] = h[choose[k]].second;
				}

				int p[6],q[6];
				for (int k = 0; k < n; k++){
					p[k] = k;
				}

				int u = 0;
				do{
					int c = 0;
					int v[6];
					if (c == 0) for (int k = 0; k < n; k++){
						if (s[k] <= p[k] && p[k] <= e[k]) c++;
						else break;
					}
					if (c == n){
						++u;
						for (int k = 0; k < n; k++) q[k] = p[k];
					}
				} while (next_permutation(p, p + n));

				if (u <= 1){
					for (int k = 0; k < n; k++){
						P[alc[k]] = pos[k][q[k]];
					}
					break;
				}
				else{
					auto& w = wow[choose];
					int last = w.first;
					int p = w.second;
					for (int k = 0; k < n; k++) if (choose[k] == last){
						if (Compare(alc[k], one[p]) == -1){
							e[k] = p;
						}
						else{
							s[k] = p + 1;
						}
						choose[k] = c[s[k]][e[k]];
						break;
					}
				}
			}
		}
	}

	vector<int> R(N);
	for (int i = 0; i < N; i++) P[i]++;
	return P;
}

Compilation message

taster.cpp: In function 'int minComp(std::vector<int>)':
taster.cpp:32:7: warning: unused variable 'v' [-Wunused-variable]
   int v[6];
       ^
taster.cpp: In function 'std::vector<int> SortWines(int, std::vector<int>)':
taster.cpp:178:10: warning: unused variable 'v' [-Wunused-variable]
      int v[6];
          ^
taster.cpp:162:8: warning: unused variable 'u' [-Wunused-variable]
    int u = minComp(choose);
        ^

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 644 KB Correct
2 Correct 10 ms 644 KB Correct
3 Correct 9 ms 908 KB Correct
4 Correct 9 ms 1032 KB Correct
5 Execution timed out 1100 ms 780 KB Time limit exceeded
6 Halted 0 ms 0 KB -