Submission #1368832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368832		altern23	Library (JOI18_library)	C++20	100 / 100	103 ms	468 KiB

library

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

#define ll long long

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

      vector <int> adj[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);
                  for (int j=0; j<=mid; j++) {
                        M[j] = 1;
                  }
                  ll cnt = mid+1;
                  for (int j=0; j<=mid; j++) {
                        for (auto x : adj[j]) cnt -= (j<x && x<=mid);
                  }
                  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);
                  for (int j=mid; j<=L; j++) {
                        M[j] = 1;
                  }
                  ll cnt = L-mid+1;
                  for (int j=mid; j<=L; j++) {
                        for (auto x : adj[j]) cnt -= (j<x && mid<=x && x<=L);
                  }
                  if (Query(M) != cnt) {
                        R = mid;
                        lf = mid+1;
                  }
                  else rg = mid-1;
            }

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

      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);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81