Submission #202421

#	Time	Username	Problem	Language	Result	Execution time	Memory
202421		EntityIT	Library (JOI18_library)	C++14	0 / 100	454 ms	516 KiB

library

#include "library.h"
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

int n;
vector<int> pref;
bool query(int be, int en, int i) {
  vector<int> ele(n, 0);
  fill(ele.begin() + be, ele.begin() + en, 1);
  int prv = (be == en ? -1 : (be == 0 ? pref[en - 1] : Query(ele) ) );
  ele[i] = 1;
  int cur = Query(ele);
  return cur <= prv;
}

void Solve(int N) {
  n = N;
  pref.assign(n, 0);
  vector<int> cur(n, 0);
  for (int i = 0; i < n; ++i) {
    cur[i] = 1;
    pref[i] = Query(cur);
  }

  vector<vector<int> > gr(N);
  for (int i = 1; i < N; ++i) if (query(0, i, i) ) {
    int l = 0, r = i - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (query(0, mid + 1, i) ) r = mid;
      else l = mid + 1;
    }

    gr[i].emplace_back(l);
    gr[l].emplace_back(i);

    if (query(l + 1, i, i) ) {
      int be = l + 1;
      l = be; r = i - 1;
      while (l < r) {
        int mid = (l + r) >> 1;
        if (query(be, mid + 1, i) ) r = mid;
        else l = mid + 1;
      }

      gr[i].emplace_back(l);
      gr[l].emplace_back(i);
    }
  }

  int rt = -1;
  for (int u = 0; u < N; ++u) if (sz(gr[u]) == 1) rt = u;

  assert(rt != -1);
  vector<bool> vis(N);
  vector<int> ans;
  for (int u = rt; u != -1; ) {
    vis[u] = true;
    ans.emplace_back(u);

    int nxt = -1;
    for (int v : gr[u]) if (!vis[v]) nxt = v;
    u = nxt;
  }
  for (auto &i : ans) ++i;

  Answer(ans);
}

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