BOJ 21821 - Acowdemia II

BOJ 21821 - Acowdemia II

개인적으로 실버치곤 어려운 문제

junior $\leftrightarrow$ senior 의관계가 되려면 앞에 나오는 이름이 더 사전순으로 늦어야한다.

어떤 리스트가 있으면 오름차순이 되는 구간으로 모두 쪼갠다.

그러면 왼쪽에 있는 구간에 있는 모든 소들은 오른쪽에 있는 모든 구간의 모든 소보다 항상 Junior이다.

이 관계를 이용해 $O(N^3)$에 푼다.

void solve() {
   int K, N;
   cin >> K >> N;
   unordered_map<string, int> idx;
   for (int i = 0; i < N; i++) {
      string name;
      cin >> name;
      idx[name] = i;
   }
   vector<vs> a(K, vs(N));
   for (int i = 0; i < K; i++) {
      fv(a[i]);
   }
   vs ans(N, string(N, '?'));

   for (int c = 0; c < K; c++) {
      vector<vs> group;
      vs g;
      for (int i = 0; i < N; i++) {
         int j = i + 1;
         g.pb(a[c][i]);
         while (j < N && g.back() < a[c][j]) g.pb(a[c][j++]);
         group.pb(g);
         g.clear();
         i = j - 1;
      }
      for (int i = 0; i < sz(group); i++) {
         for (int j = i + 1; j < sz(group); j++) {
            for (string& I: group[i]) {
               for (string& J: group[j]) {
                  ans[idx[I]][idx[J]] = '0';
                  ans[idx[J]][idx[I]] = '1';
               }
            }
         }
      }
   }
   for (int i = 0; i < N; i++) ans[i][i] = 'B';
   for (int y = 0; y < N; y++) cout << ans[y] << endl;
}