oj.uz

Submission #963190

# Submission time Handle Problem Language Result Execution time Memory
963190 2024-04-14T16:48:25 Z abczz Library (JOI18_library) C++14
0 / 100
 1 ms 440 KB 
#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;
    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);
    for (int j=0; j<n; ++j) {
      if (!B[j]) Q[j] ^= 1;
    }
    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;
    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);
      for (int j=0; j<N; ++j) {
        if (!B[j]) Q[j] ^= 1;
      }
      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);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:72:32: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     else X.push_back({binsearch(l, mid), binsearch(mid+1, r)});
      |                       ~~~~~~~~~^~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -