Submission #148516

#	Time	Username	Problem	Language	Result	Execution time	Memory
148516		ProofByTLE (#200)	List of Unique Integers (FXCUP4_unique)	C++17	100 / 100	6 ms	512 KiB

unique

#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;
}

• Subtask 1: 100 / 100