Submission #44052

#	Time	Username	Problem	Language	Result	Execution time	Memory
44052		wxh010910	Library (JOI18_library)	C++17	100 / 100	433 ms	844 KiB

library

#include "library.h"

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 1005;

vector <int> qry, ans;
int n, val[N << 2];
set <int> adj[N];
bool vis[N];

inline void Build(int x, int l, int r) {
  if (l == r) {
    val[x] = 1;
    return ;
  }
  for (int i = 1; i <= n; ++i) {
    qry[i - 1] = i >= l && i <= r;
  }
  val[x] = Query(qry);
  int mid = l + r >> 1;
  Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r);
}

inline void Query(int x, int l, int r, int v) {
  if (r <= v || adj[v].size() == 2) {
    return ;
  }
  if (v == l && v == r) {
    return ;
  }
  if (v >= l && v <= r) {
    for (int i = 1; i <= n; ++i) {
      qry[i - 1] = i >= l && i <= r && i != v;
    }
    if (Query(qry) + 1 == val[x]) {
      return ;
    }
  } else {
    for (int i = 1; i <= n; ++i) {
      qry[i - 1] = (i >= l && i <= r) || (i == v);
    }
    if (Query(qry) == val[x] + 1) {
      return ;
    }
  }
  if (l == r) {
    adj[v].insert(l), adj[l].insert(v);
    return ;
  }
  int mid = l + r >> 1;
  Query(x << 1, l, mid, v), Query(x << 1 | 1, mid + 1, r, v);
}

inline void DFS(int x) {
  ans.pb(x), vis[x] = true;
  for (auto y : adj[x]) {
    if (!vis[y]) {
      DFS(y);
    }
  }
}

void Solve(int N) {
  qry.resize(N), n = N, Build(1, 1, n);
  if (n == 1) {
    Answer(vector <int> {1});
    return ;
  }
  for (int i = 1; i <= n; ++i) {
    Query(1, 1, n, i);
  }
  for (int i = 1; i <= n; ++i) {
    if (adj[i].size() == 1) {
      DFS(i), Answer(ans);
      return ;
    }
  }
}

Compilation message (stderr)

library.cpp: In function 'void Build(int, int, int)':
library.cpp:59:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
library.cpp: In function 'void Query(int, int, int, int)':
library.cpp:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

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