14653 너의 이름은

14654 너의 이름은 https://www.acmicpc.net/problem/14653

카카오 톡 방처럼 N개의 메세지에서 보낸사람과 읽지않은 사람 수가 주어진다.
Q번째 메세지를 읽지 않았을 가능성이 있는사람을 구하는 문제이다.

Q번째 메세지를 확실히 읽은 사람은 3가지 경우가 있다.
1. 문제에 제시된 'A'
2. Q번째 메세지 이후로 메세지를 보낸 사람들
3. Q번째 메세지의 읽지않은 사람 수와 같은 메세지를 보낸 사람들

#include <cstdio> #include <vector> using namespace std; int N, M, K; bool f[10001]; int message[10001][2]; int sum[27]; vector<char> ans; int main() {     scanf("%d%d%d", &N, &M, &K);       for (int m = 0;m < M;m++) {         char c;         scanf("%d %c", &message[m][0], &c);         message[m][1] = c - 'A';         sum[c - 'A']++;     }     for (int m = 0;m < M;m++)         if (message[m][0] == message[K - 1][0])             f[message[m][1]] = true;     for (int k = 0;k < K;k++) {         if (k == K - 1) {             for (int n = 0;n < N;n++) {                 if (!sum[n] && !f[n] && n != 0)                     ans.push_back(n + 'A');             }         }         sum[message[k][1]]--;     }     if (ans.empty() || message[K - 1][0] == 0) printf("-1\n");     else         for (auto n : ans) printf("%c ", n);       return 0; } Colored by Color Scripter

cs