oj.uz

Submission #963192

# Submission time Handle Problem Language Result Execution time Memory
963192 2024-04-14T16:54:56 Z abczz Library (JOI18_library) C++14
100 / 100
 325 ms 688 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;
    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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 436 KB # of queries: 2437
2 Correct 23 ms 436 KB # of queries: 2460
3 Correct 23 ms 440 KB # of queries: 2596
4 Correct 23 ms 436 KB # of queries: 2569
5 Correct 22 ms 436 KB # of queries: 2559
6 Correct 26 ms 428 KB # of queries: 2601
7 Correct 31 ms 600 KB # of queries: 2571
8 Correct 23 ms 688 KB # of queries: 2517
9 Correct 30 ms 436 KB # of queries: 2550
10 Correct 13 ms 432 KB # of queries: 1407
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 1 ms 344 KB # of queries: 4
14 Correct 1 ms 344 KB # of queries: 11
15 Correct 1 ms 344 KB # of queries: 88
16 Correct 1 ms 344 KB # of queries: 178

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 436 KB # of queries: 2437
2 Correct 23 ms 436 KB # of queries: 2460
3 Correct 23 ms 440 KB # of queries: 2596
4 Correct 23 ms 436 KB # of queries: 2569
5 Correct 22 ms 436 KB # of queries: 2559
6 Correct 26 ms 428 KB # of queries: 2601
7 Correct 31 ms 600 KB # of queries: 2571
8 Correct 23 ms 688 KB # of queries: 2517
9 Correct 30 ms 436 KB # of queries: 2550
10 Correct 13 ms 432 KB # of queries: 1407
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 1 ms 344 KB # of queries: 4
14 Correct 1 ms 344 KB # of queries: 11
15 Correct 1 ms 344 KB # of queries: 88
16 Correct 1 ms 344 KB # of queries: 178
17 Correct 301 ms 448 KB # of queries: 17322
18 Correct 311 ms 444 KB # of queries: 17079
19 Correct 306 ms 440 KB # of queries: 17210
20 Correct 267 ms 444 KB # of queries: 16188
21 Correct 256 ms 444 KB # of queries: 15127
22 Correct 325 ms 444 KB # of queries: 17320
23 Correct 306 ms 444 KB # of queries: 17330
24 Correct 111 ms 440 KB # of queries: 7881
25 Correct 299 ms 440 KB # of queries: 16762
26 Correct 266 ms 440 KB # of queries: 15694
27 Correct 106 ms 436 KB # of queries: 7802
28 Correct 252 ms 676 KB # of queries: 15019
29 Correct 252 ms 444 KB # of queries: 14996
30 Correct 226 ms 448 KB # of queries: 15019