답안 #112981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
112981 2019-05-23T01:49:21 Z imsifile 포도주 시음 (FXCUP4_wine) C++17
컴파일 오류
0 ms 0 KB
#include "bartender.h"
using namespace std;

void BlendWines(int N, int K, vector<int> R, vector<int> &A){
	for(int i=0; i<N; i++){
		if(R[i] > 12) A[i] = R[i]-11;
		else R[i] = 1;
	}
	// 1 ~ 19
}
#include "taster.h"
#include <algorithm>
#include <string>
using namespace std;

int N, ba[22], bcn;

int comp(int a, int b){ // if a<b, 1.
	if(a>N || b>N) return a<b;
	return Compare(a,b) < 0;
}

vector<string> ss;
void dfs(int ix, int chk, string s){
	if(ix==10){
		ss.push_back(s);
		return;
	}
	int mi=0;
	if(ix>=5) mi=s[ix-5]-'0'+1;
	else if(ix) mi=s[ix-1]-'0'+1;
	for(int i=mi; i<=9; i++){
		if(chk&(1<<i)) continue;
		dfs(ix+1, chk|(1<<i), s+char('0'+i));
	}
}

int cmd[9999][2]; string res[9999];
int getdepth(vector<string> v, int ix, int req){
	if(v.size() <= 1){
		if(v.size() == 1) res[ix] = v[0];
		return 1;
	}
	if((int)v.size() > (1<<req)) return 0;
	vector<string> v1, v2;
	for(int i=0; i<10; i++){
		for(int j=i+1; j<10; j++){
			v1.clear(), v2.clear();
			for(auto &s: v){
				if(s[i]<s[j]) v1.push_back(s);
				else v2.push_back(s);
			}
			if(getdepth(v1, ix*2, req-1) && getdepth(v2, ix*2+1, req-1)){
				cmd[ix][0]=i, cmd[ix][1]=j;
				return 1;
			}
		}
	}
	return 0;
}

void ins(int *v, int sz){
	int mi=0, mx=sz-1, md, cu=sz;
	while(mi<=mx){
		md=(mi+mx)/2;
		if(comp(v[sz],v[md])) cu=md, mx=md-1;
		else mi=md+1;
	}
	reverse(v+cu, v+sz+1);
	reverse(v+cu+1, v+sz+1);
}

void swap2(int *v, int ix1, int ix2){
	swap(v[ix1], v[ix2]);
	swap(v[ix1+5], v[ix2+5]);
}

void smsort(int *v, int sz){
	if(sz == 5){
		if(!comp(v[0], v[1])) swap2(v, 0, 1);
		if(!comp(v[2], v[3])) swap2(v, 2, 3);
		if(!comp(v[0], v[2])) swap2(v, 0, 2), swap2(v, 1, 3);
		if(comp(v[2], v[4])){
			if(!comp(v[3], v[4])) swap2(v, 3, 4);
			// a b cde
			if(comp(v[1], v[3])){
				if(!comp(v[1], v[2])) swap2(v, 1, 2);
			}
			else{
				swap2(v, 1, 2); swap2(v, 2, 3); // acd b e
				if(!comp(v[3], v[4])) swap2(v, 3, 4);
			}
		}
		else{
			swap2(v, 3, 4); swap2(v, 2, 3);
			if(comp(v[0], v[2])){
				// a b ecd
				if(comp(v[1], v[3])){
					if(!comp(v[1], v[2])) swap2(v, 1, 2);
				}
				else{
					swap2(v, 1, 2); swap2(v, 2, 3); // aec b d
					if(!comp(v[3], v[4])) swap2(v, 3, 4);
				}
			}
			else{
				swap2(v, 1, 2), swap2(v, 0, 1); // ea b cd
				if(!comp(v[2], v[3])){
					swap2(v, 2, 3);
					if(!comp(v[3], v[4])) swap2(v, 3, 4);
				}
			}
		}
	}
	if(sz == 10){
		for(int i=0; i<5; i++){
			if(!comp(v[i],v[i+5])) swap(v[i],v[i+5]);
		}
		smsort(v,5);

		int st=1;
		while(cmd[st][0]!=cmd[st][1]){
			if(comp(v[cmd[st][0]], v[cmd[st][1]])) st=st*2;
			else st=st*2+1;
		}
		string x = res[st];
		for(int i=0; i<9; i++){
			int j;
			for(j=i; j<10; j++){
				if(x[j]==i+'0') break;
			}
			swap(v[i],v[j]), swap(x[i],x[j]);
		}
	}
	if(sz == 12) smsort(v,10), ins(v,10), ins(v,11);
}

void SortWines(int N_, int K, vector<int> A, vector<int> &R) {
	dfs(0,0,"");
	getdepth(ss,1,10);

	N = N_;
	R.resize(N);
	if(N <= 12){
		for(int i=1; i<=12; i++) ba[i-1]=i;
		smsort(ba, 12);
		for(int i=0; i<N; i++) R[ba[i]-1]=i+1;
		return;
	}
	for(int i=0; i<N; i++){
		if(A[i]==1) ba[bcn++]=i+1;
		else R[i]=A[i]+11;
	}
	smsort(ba, 12);
	for(int i=0; i<12; i++) R[ba[i]-1]=i+1;
}

Compilation message

/tmp/ccY7B33Z.o: In function `main':
grader_b.cpp:(.text.startup+0x1a1): undefined reference to `BlendWines(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status

/tmp/ccEcRYKK.o: In function `main':
grader_t.cpp:(.text.startup+0x1b4): undefined reference to `SortWines(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status