Submission #43982

#	Time	Username	Problem	Language	Result	Execution time	Memory
43982		azneye	Library (JOI18_library)	C++17	100 / 100	703 ms	60348 KiB

library

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

using namespace std;

namespace {
#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define RARA(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define VERA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef int ll;

void DFS(const vector<vector<ll>>& adj, ll at, vector<bool>& vis, vector<ll>& res) {
  if (vis[at])
    return;
  res.push_back(at);
  vis[at] = true;
  VERA(to, adj[at]) {
    DFS(adj, to, vis, res);
  }
}

map<vector<ll>, ll> cache;

ll MyQuery(const vector<ll>& ques) {
  if (count(ALL(ques), 1) == 0) return 0;
  auto it = cache.find(ques);
  if (it == cache.end()) {
    const ll res = Query(ques);
    cache.emplace(ques, res);
    return res;
  } else {
    return it->second;
  }
}

}

void Solve(int N) {
  if (N == 1) {
    Answer({1});
    return;
  }
  vector<vector<ll>> adj(N);
  vector<ll> ques(N);
  set<ll> ends;
  VEVE(k, 0, N) {
    if (SIZE(adj[k]) == 2)
      continue;
    if (SIZE(ends) < 2) {
      fill(ALL(ques), 1);
      ques[k] = 0;
      if (MyQuery(ques) == 1) {
        ends.insert(k);
        if (SIZE(adj[k]) == 1)
          continue;
      }
    }
    while (SIZE(adj[k]) < 2 - ends.count(k)) {
      ll low = 0, hig = N - 1;
      while (low < hig) {
        const ll mid = (low + hig) / 2;
        // is k adjacent to book in [low,mid]?
        fill(ALL(ques), 0);
        VEVE(i, low, mid + 1) ques[i] = 1;
        VERA(to, adj[k]) ques[to] = 0;
        ques[k] = 0;
        const ll cnt_without = MyQuery(ques);
        ques[k] = 1;
        const ll cnt_with = MyQuery(ques);
        if (cnt_with <= cnt_without) {
          hig = mid;
        } else {
          low = mid + 1;
        }
      }
//      DEBUG(k + 1, hig + 1);
      adj[k].push_back(hig);
      adj[hig].push_back(k);
    }
  }
  vector<ll> res;
  vector<bool> vis(N, false);
  VEVE(v, 0, N) if (SIZE(adj[v]) == 1) {
      DFS(adj, v, vis, res);
      break;
    }
  VERA(r, res) ++r;
//  DEBUG(res);
  Answer(res);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:61:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (SIZE(adj[k]) < 2 - ends.count(k)) {
                         ^

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