#include "unique.h"
#include <stdio.h>
std::vector<int> PickUnique(int N) {
std::vector<int> answer(N, 0);
// Iterate: prefix[i]: [0~i], suffix[i]: [i~end)
std::vector<int> prefixUniqueCount(N, 0), suffixUniqueCount(N, 0);
for(int left=0; left<N-1; left++){
suffixUniqueCount[left] = UniqueCount(left, N-1);
prefixUniqueCount[left+1] = UniqueCount(0, left+1);
}
prefixUniqueCount[0] = 1; suffixUniqueCount.back() = 1;
//printf("Prefix: "); for(auto it: prefixUniqueCount) printf("%d, ", it); printf("\n");
//printf("Suffix: "); for(auto it: suffixUniqueCount) printf("%d, ", it); printf("\n");
for(int mid=0; mid<N; mid++){
bool left = false, right = false;
// Left
if(mid == 0) left = true;
else if(prefixUniqueCount[mid-1] == prefixUniqueCount[mid] - 1) left = true;
// Right
if(mid == N-1) right = true;
else if(suffixUniqueCount[mid+1] == suffixUniqueCount[mid] - 1) right = true;
answer[mid] = (int)(left && right);
}
return answer;
}
