oj.uz

Submission #148516

# Submission time Handle Problem Language Result Execution time Memory
148516 2019-09-01T04:35:01 Z ProofByTLE(#3614, Mahotsukai, McDic, Redux) List of Unique Integers (FXCUP4_unique) C++17
100 / 100
 6 ms 512 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Correct : C = 2
2 Correct 5 ms 256 KB Correct : C = 8
3 Correct 5 ms 256 KB Correct : C = 48
4 Correct 5 ms 384 KB Correct : C = 98
5 Correct 5 ms 384 KB Correct : C = 98
6 Correct 5 ms 384 KB Correct : C = 152
7 Correct 5 ms 384 KB Correct : C = 198
8 Correct 5 ms 384 KB Correct : C = 298
9 Correct 5 ms 384 KB Correct : C = 354
10 Correct 5 ms 512 KB Correct : C = 398
11 Correct 5 ms 512 KB Correct : C = 398
12 Correct 5 ms 512 KB Correct : C = 398
13 Correct 6 ms 512 KB Correct : C = 398
14 Correct 5 ms 512 KB Correct : C = 398
15 Correct 5 ms 432 KB Correct : C = 398