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