Submission #963192

#	Time	Username	Problem	Language	Result	Execution time	Memory
963192		abczz	Library (JOI18_library)	C++14	100 / 100	325 ms	688 KiB

library

#include <iostream>
#include <cstdio>
#include <array>
#include <vector>
#include "library.h"
#define ll long long
using namespace std;

bool B[1000];
vector <array<ll, 2>> X;
ll n;

ll binsearch(ll ul, ll ur) {
  vector <int> Q(n);
  ll a, b, cnt = 0;
  while (ul < ur) {
    ll mid = (ul + ur) / 2;
    cnt = 0;
    for (int j=0; j<n; ++j) {
      if (ul <= j && j <= mid && !B[j]) {
        ++cnt;
        Q[j] = 1;
      }
      else Q[j] = 0;
    }
    if (!cnt) {
      ul = mid+1;
      continue;
    }
    a = Query(Q);
    cnt = 0;
    for (int j=0; j<n; ++j) {
      if (!B[j]) Q[j] ^= 1;
      if (Q[j] == 1) ++cnt;
    }
    if (!cnt) {
      ur = mid;
      continue;
    }
    b = Query(Q);
    if (a == b) ur = mid;
    else ul = mid+1;
  }
  return ul;
}
void Solve(int N)
{
  X.clear();
  n = N;
  ll l, r, mid, a, b, cnt;
  vector <int> Q(N), F(N);
  for (int i=0; i<N; ++i) B[i] = 0;
  for (int i=0; i<N/2; ++i) {
    l = 0, r = N-1;
    while (l+1 < r) {
      mid = (l+r)/2;
      cnt = 0;
      for (int j=0; j<N; ++j) {
        if (l <= j && j <= mid && !B[j]) {
          ++cnt;
          Q[j] = 1;
        }
        else Q[j] = 0;
      }
      if (!cnt) {
        l = mid+1;
        continue;
      }
      a = Query(Q);
      cnt = 0;
      for (int j=0; j<N; ++j) {
        if (!B[j]) Q[j] ^= 1;
        if (Q[j] == 1) ++cnt;
      }
      if (!cnt) {
        r = mid;
        continue;
      }
      b = Query(Q);
      if (a == b) break;
      if (a > b) r = mid;
      else l = mid+1;
    }
    if (l+1 == r) X.push_back({l, r});
    else X.push_back({binsearch(l, mid), binsearch(mid+1, r)});
    B[X.back()[0]] = B[X.back()[1]] = 1;
  }
  for (int i=0; i<N; ++i) {
    if (!B[i]) F[N/2] = i+1;
  }
  if (!X.empty()) F[0] = X[0][0]+1, F[N-1] = X[0][1]+1;
  for (int i=1; i<N/2; ++i) {
    for (int j=0; j<N; ++j) {
      Q[j] = 0;
      if (j == F[i-1]-1 || j == X[i][0]) Q[j] = 1;
    }
    a = Query(Q);
    F[i] = X[i][0]+1, F[N-1-i] = X[i][1]+1;
    if (a == 2) swap(F[i], F[N-1-i]);
  }
  Answer(F);
}

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