#include <iostream> #include <stdio.h> using namespace std; void swap(int* array, int i, int j) { int number = array[i]; array[i] = array[j]; array[j] = number; } void sort(int* array, int leftBound, int rightBound) { if (leftBound >= rightBound) { return; } int left = leftBound; int right = rightBound; swap(array, left, (left + right) / 2); while (left < right) { if (array[left] < array[left + 1]) { swap(array, left + 1, right); right--; } else { swap(array, left, left + 1); left++; } } sort(array, leftBound, left - 1); sort(array, right + 1, rightBound); } void sort(int* array, int n) { sort(array, 0, n - 1); } int MAX = 1000000001; int limit(int number) { return number > MAX ? MAX : number; } int main() { int nFishes; nFishes; cin >> nFishes; // read data int weightOfFish[nFishes]; int backup[nFishes]; for (int iFish = 0; iFish < nFishes; iFish++) { int weight; cin >> weight; weightOfFish[iFish] = weight; backup[iFish] = weight; } sort(weightOfFish, nFishes); // corner case if (nFishes == 1) { printf("T"); return 0; } int iKing = 0; int totalWeight = weightOfFish[0]; for (int iFish = 1; iFish < nFishes; iFish++) { int iWeight = weightOfFish[iFish]; if (totalWeight <= iWeight) { iKing = iFish; } totalWeight += iWeight; if (totalWeight > MAX) { break; } } // int minimalWeight = weightOfFish[iKing]; if (minimalWeight == weightOfFish[0]) { minimalWeight++; } // print for (int i = 0; i < nFishes; i++) { if (backup[i] >= minimalWeight) { printf("T"); } else { printf("N"); } } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | #include <iostream> #include <stdio.h> using namespace std; void swap(int* array, int i, int j) { int number = array[i]; array[i] = array[j]; array[j] = number; } void sort(int* array, int leftBound, int rightBound) { if (leftBound >= rightBound) { return; } int left = leftBound; int right = rightBound; swap(array, left, (left + right) / 2); while (left < right) { if (array[left] < array[left + 1]) { swap(array, left + 1, right); right--; } else { swap(array, left, left + 1); left++; } } sort(array, leftBound, left - 1); sort(array, right + 1, rightBound); } void sort(int* array, int n) { sort(array, 0, n - 1); } int MAX = 1000000001; int limit(int number) { return number > MAX ? MAX : number; } int main() { int nFishes; nFishes; cin >> nFishes; // read data int weightOfFish[nFishes]; int backup[nFishes]; for (int iFish = 0; iFish < nFishes; iFish++) { int weight; cin >> weight; weightOfFish[iFish] = weight; backup[iFish] = weight; } sort(weightOfFish, nFishes); // corner case if (nFishes == 1) { printf("T"); return 0; } int iKing = 0; int totalWeight = weightOfFish[0]; for (int iFish = 1; iFish < nFishes; iFish++) { int iWeight = weightOfFish[iFish]; if (totalWeight <= iWeight) { iKing = iFish; } totalWeight += iWeight; if (totalWeight > MAX) { break; } } // int minimalWeight = weightOfFish[iKing]; if (minimalWeight == weightOfFish[0]) { minimalWeight++; } // print for (int i = 0; i < nFishes; i++) { if (backup[i] >= minimalWeight) { printf("T"); } else { printf("N"); } } return 0; } |