제출 #1368830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368830		altern23	도서관 (JOI18_library)	C++20	0 / 100	7 ms	424 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

#define ll long long

struct DSU {
      ll N;
      vector <ll> par;
      
      DSU (ll _n) {
            N = _n;
            par.resize(N+5);
            iota(par.begin(), par.end(), 0LL);
      }

      ll find(ll idx) {
            return par[idx] == idx ? idx : par[idx] = find(par[idx]);
      }

      void join(ll a, ll b) {
            a = find(a), b = find(b);
            if (a == b) return;
            par[b] = a;
      }
};

void Solve(int N) {
      if (N == 1) {
            Answer({1});
            return;
      }

      vector <int> adj[N];

      DSU dsu(N);
      
      for (int i=0; i<N-1; i++) {
            ll lf = 0, rg = N-1, L = -1, R = -1;
            while (lf<=rg) {
                  ll mid = (lf+rg)/2;
                  vector <int> M(N), vis(N);
                  ll cnt = 0;
                  for (int j=0; j<=mid; j++) {
                        M[j] = 1;
                        cnt += !vis[dsu.find(j)];
                        vis[dsu.find(j)] = 1;
                  }
                  if (Query(M) != cnt) {
                        L = mid;
                        rg = mid-1;
                  }
                  else lf = mid+1;
            }

            lf = 0, rg = L-1;
            while (lf<=rg) {
                  ll mid = (lf+rg)/2;
                  vector <int> M(N), vis(N);
                  ll cnt = 0;
                  for (int j=mid; j<=L; j++) {
                        M[j] = 1;
                        cnt += !vis[dsu.find(j)];
                        vis[dsu.find(j)] = 1;
                  }
                  if (Query(M) != cnt) {
                        R = mid;
                        lf = mid+1;
                  }
                  else rg = mid-1;
            }

            adj[L].push_back(R);
            adj[R].push_back(L);

            dsu.join(L, R);
      }

      vector <int> res;

      for (int i=0; i<N; i++) {
            if (adj[i].size() == 1) {

                  ll idx = i, lst = -1;
                  while (true) {
                        bool ch = 0;
                        res.push_back(idx+1);
                        for (auto x : adj[idx]) {
                              if (x != lst) {
                                    lst = idx;
                                    idx = x;
                                    ch = 1;
                                    break;
                              }
                        }
                        if (!ch) break;
                  }
                  break;
            }
      }
      
	Answer(res);
}

• 서브태스크 1: 0 / 19
• 서브태스크 2: 0 / 81