#define _CRT_SECURE_NO_WARNINGS #include #include #include #define R 31 #define M 1000000 typedef struct log { char name[6]; int hashNum; } log; log history[M], left[M / 2], right[M / 2]; char attendance[M]; int hashFunc(char* str); void merge_sort(int start, int end); void merge(int start, int middle, int end); int main(void) { int cnt, hash, nameIdx = 0; char command[6], name[6]; scanf("%d", &cnt); for (int i = 0; i < cnt; i++) { scanf("%s %s", name, command); hash = hashFunc(name); if (command[0] == 'e') { if (attendance[hash] != 'N' && attendance[hash] != 'Y') { history[nameIdx].hashNum = hash; strcpy(history[nameIdx++].name, name); attendance[hash] = 'Y'; } } else { attendance[hash] = 'N'; } } merge_sort(0, nameIdx - 1); for (int i = 0; i < nameIdx; i++) { if (attendance[history[i].hashNum] == 'Y') { printf("%s\n", history[i].name); } } return 0; } int hashFunc(char* str) { int expo = 1, res = 0; for (int i = 0; str[i] != '\0'; i++) { for (int j = 0; j <= i; j++) { expo = (expo * R) % M; } res += (str[i] * expo) % M; res %= M; } return res; } void merge_sort(int start, int end) { int middle = (start + end) / 2; if (start < end) { merge_sort(start, middle); merge_sort(middle + 1, end); merge(start, middle, end); } } void merge(int start, int middle, int end) { int leftIdx = 0, rightIdx = 0, tmp; for (int i = start; i < middle + 1; i++) { left[leftIdx].hashNum = history[i].hashNum; strcpy(left[leftIdx++].name, history[i].name); } for (int i = middle + 1; i <= end; i++) { right[rightIdx].hashNum = history[i].hashNum; strcpy(right[rightIdx++].name, history[i].name); } left[leftIdx].name[0] = '\0'; right[rightIdx].name[0] = '\0'; leftIdx = 0; rightIdx = 0; for (int i = start; i <= end; i++) { if (left[leftIdx].name[0] != '\0' && right[rightIdx].name[0] != '\0') { if (strcmp(left[leftIdx].name, right[rightIdx].name) < 0) { history[i].hashNum = right[rightIdx].hashNum; strcpy(history[i].name, right[rightIdx++].name); } else { history[i].hashNum = left[leftIdx].hashNum; strcpy(history[i].name, left[leftIdx++].name); } } else if (right[rightIdx].name[0] == '\0') { history[i].hashNum = left[leftIdx].hashNum; strcpy(history[i].name, left[leftIdx++].name); } else { history[i].hashNum = right[rightIdx].hashNum; strcpy(history[i].name, right[rightIdx++].name); } } }

제출 #89567

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: