Submission #218088

#	Time	Username	Problem	Language	Result	Execution time	Memory
218088		extraterrestrial	Library (JOI18_library)	C++14	100 / 100	247 ms	508 KiB

library

#include "library.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()

int my_query(vector<int> x, int n) {
  vector<int> m(n, 0);
  for (auto it : x) {
    m[it - 1] = 1;
  }
  return Query(m);
}

void Solve(int n) {
  if (n == 1) {
    Answer({1});
    return;
  }
  vector<vector<int>> g(n + 1);
	vector<vector<int>> segs;
  vector<int> fs = {1}, en = {1};
  segs.pb({1});
  for (int i = 2; i <= n; i++) {
    vector<int> m(n, 0);
    for (int j = 0; j < i; j++) {
      m[j] = 1;
    }
    int rs = Query(m);
    if (rs == SZ(segs) + 1) {
      segs.pb({i});
      fs.pb({i});
      en.pb({i});
      continue;
    }
    else if (rs == SZ(segs)) {
      int l = -1, r = SZ(segs) - 1;
      while (r - l > 1) {
        int mid = (l + r) / 2;
        fill(all(m), 0);
        for (int j = 0; j <= mid; j++) {
          for (auto it : segs[j]) {
            m[it - 1] = 1;
          }
        }
        m[i - 1] = 1;
        if (Query(m) == mid + 1) {
          r = mid;
        }
        else {
          l = mid;
        }
      }
      if (my_query({fs[r], i}, n) == 1) {
        g[fs[r]].pb(i);
        g[i].pb(fs[r]);
        fs[r] = i;
      }
      else {
        g[en[r]].pb(i);
        g[i].pb(en[r]);
        en[r] = i;
      }
      segs[r].pb(i);
    }
    else {
      int l = -1, r = SZ(segs) - 1;
      while (r - l > 1) {
        int mid = (l + r) / 2;
        fill(all(m), 0);
        for (int j = 0; j <= mid; j++) {
          for (auto it : segs[j]) {
            m[it - 1] = 1;
          }
        }
        m[i - 1] = 1;
        if (Query(m) <= mid + 1) {
          r = mid;
        }
        else {
          l = mid;
        } 
      }
      int id1 = r, id2;
      l = r;
      r = SZ(segs) - 1;
      while (r - l > 1) {
        int mid = (l + r) / 2;
        fill(all(m), 0);
        for (int j = id1 + 1; j <= mid; j++) {
          for (auto it : segs[j]) {
            m[it - 1] = 1;
          }
        }
        m[i - 1] = 1;
        if (Query(m) == mid - id1) {
          r = mid;
        }
        else {
          l = mid;
        } 
      }
      id2 = r;
      vector<vector<int>> nsegs;
      vector<int> nfs, nen;
      for (int j = 0; j < SZ(segs); j++) {
        if (j != id1 && j != id2) {
          nsegs.pb(segs[j]);
          nfs.pb(fs[j]);
          nen.pb(en[j]);
        }
      }
      nsegs.pb({i});
      for (auto it : segs[id1]) {
        nsegs.back().pb(it);
      }
      for (auto it : segs[id2]) {
        nsegs.back().pb(it);
      }
      if (my_query({fs[id1], i}, n) == 1) {
        g[i].pb(fs[id1]);
        g[fs[id1]].pb(i);
        nfs.pb(en[id1]);
      }
      else {
        g[i].pb(en[id1]);
        g[en[id1]].pb(i);
        nfs.pb(fs[id1]);
      }
      if (my_query({fs[id2], i}, n) == 1) {
        g[i].pb(fs[id2]);
        g[fs[id2]].pb(i);
        nen.pb(en[id2]);
      }
      else {
        g[i].pb(en[id2]);
        g[en[id2]].pb(i);
        nen.pb(fs[id2]);
      }
      segs = nsegs;
      fs = nfs;
      en = nen;
    }
    /*cerr << i << ' ' << SZ(segs) << endl;
    for (int j = 0; j < SZ(segs); j++) {
      for (auto it : segs[j]) {
        cerr << it << ' ';
      }
      cerr << endl;
    }
    cerr << endl;*/
  }
  int fst = -1;
  for (int i = 1; i <= n; i++) {
    if (SZ(g[i]) == 1) {
      fst = i;
      break;
    }
  }
  assert(fst != -1);
  vector<int> res = {fst};
  int prv = 0, cur = fst;
  for (int i = 1; i < n; i++) {
    for (int nxt : g[cur]) {
      if (nxt != prv) {
        res.pb(nxt);
        prv = cur;
        cur = nxt;
        break;
      }
    }
  }
  assert(SZ(res) == n);
  Answer(res);
}

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