#include <stdafx.h>
#include <string.h>
#include <iostream>
using namespace std;
#define MAX 1000
typedef int type;
int N, M, C, V;
type sequence[MAX];
int seqIndex;
void printSequence()
{
int iEnd = N - 1;
for(int i = 0; i < iEnd; ++i)
cout << sequence[i] << " ";
cout << sequence[iEnd];
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class TSubSeq
{
public:
type* head;
type last;
/*con*/ TSubSeq() {}
/*des*/ ~TSubSeq() { delete[] head; }
void read()
{
head = new type[M];
for(int i = 0; i < M; ++i)
cin >> head[i];
last = head[V];
}
void putHead()
{
for(int i = 0; i < M; ++i)
sequence[i] = head[i];
seqIndex = M;
}
void putLast()
{
sequence[seqIndex++] = last;
}
bool matched()
{
type* tail = sequence + seqIndex - M + 1;
for(int i = 0; i < V; ++i)
{
if(tail[i] != head[i]) return false;
}
return true;
}
};
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class Deck
{
protected:
int mCount;
public:
TSubSeq* buffer[MAX];
/* con */ Deck() : mCount(0) {}
void add(TSubSeq* some)
{
buffer[mCount++] = some;
}
int indexOf(TSubSeq* some)
{
for(int i = 0; i < C; ++i)
{
if(buffer[i] == some) return i;
}
return -1;
}
TSubSeq* pop(int index)
{
mCount--;
TSubSeq* temp = buffer[index];
buffer[index] = buffer[mCount];
return buffer[mCount] = temp;
}
TSubSeq* pop(TSubSeq* some)
{
return pop(indexOf(some));
}
int count() { return mCount; }
void refill() { mCount = C; }
void reload(TSubSeq* some) { mCount++; }
};
TSubSeq subSeqs[MAX];
Deck deck;
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void advanceFrom(TSubSeq* base)
{
for(int i = deck.count() - 1; i >= 0; --i)
{
if(deck.buffer[i]->matched())
{
TSubSeq* next = deck.pop(i);
next->putLast();
advanceFrom(next);
deck.reload(next);
if(seqIndex == N)
return;
seqIndex--;
}
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void process()
{
for(int i = 0; i < C; ++i)
deck.add(subSeqs + i);
for(int i = deck.count() - 1; i >= 0; --i)
{
TSubSeq* next = deck.pop(i);
next->putHead();
advanceFrom(next);
deck.reload(next);
if(seqIndex == N)
return;
}
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void readFile()
{
cin >> N;
cin >> M;
C = N - M + 1;
V = M - 1;
for(int i = 0; i < C; ++i)
subSeqs[i].read();
}
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int main(int argc, char* argv[])
{
#ifdef WIN32
freopen("c:\input2.txt", "r", stdin);
#endif
readFile();
process();
printSequence();
return 0;
}
로컬이면 저런거 못 풀겠냐 문제 졸라 단순한데.
뭔가 놓친게 있는것 같긴 하군.
무슨 문젠진 보지 못했지만 소스 코드 엄청 깔끔하네요. 역시 코세 성님이네요. 지리고 갑니다. freopen은 Visual C++에서만 제공되는 것인가요? 왜 WIN32 전처리기 조건문을 쓰신 거죠?
웅 vs 에서 코딩할땐 파일로 입력테스트하고 그 코딩 사이트(백준?)에 올릴땐 콘솔로 입력받게 하려고. (리눅스 베이스 서버일것 같아서)
그때 그 문제야.
부분수열 머징하는거
음... 코드에서는 정수만 처리할 수 있는데 백준 온라인 저지 사이트 테스트 케이스 중에는 99999.999999 였나 이런 실수가 입력되는 케이스도 있어서 문자열로 입력받아서 처리하시는 게 이래저래 좋아 보이네요.
실수 입력 없는것 같던데. 그리고 타잎은 typedef ~~ type 에서 정의할 수 있어.
제가 직접 Blind condition test로 알아본 결과로는 99999.999999...(...는 이 이상의 자리수는 테스트 안 해 봄) 라는 수가 입력됐던 걸로 기억해서요. ㄷㄷ 그리고 저런 식으로 실수도 입력된다고 하면 float나 double로는 표현 불가능한 실수가 입력되지 않는단 보장이 없어서 문자열로 처리하시면 깔끔할 듯 해요.