oj.uz

답안 #242623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242623 2020-06-28T11:10:54 Z WLZ 도서관 (JOI18_library) C++14
100 / 100
 538 ms 384 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

void Solve(int N) {
  if (N == 1) {
    Answer({1});
    return;
  }
  vector<int> a(N, 1);
  vector<int> ans;
  set<int> st;
  for (int i = 1; i <= N; i++) {
    st.insert(i);
  }
  for (int i = 1; i <= N; i++) {
    a[i - 1] = 0;
    if (Query(a) == 1) {
      ans.push_back(i);
      st.erase(i);
      break;
    }
    a[i - 1] = 1;
  }
  for (int t = 0; t < N - 1; t++) {
    vector<int> b;
    for (auto& x : st) {
      b.push_back(x);
    }
    int l = 0, r = (int) b.size() - 1;
    while (l < r) {
      int mid = (l + r) / 2;
      a.assign(N, 0);
      for (int i = l; i <= mid; i++) {
        a[b[i] - 1] = 1;
      }
      int tmp1 = Query(a);
      a[ans.back() - 1] = 1;
      int tmp2 = Query(a);
      if (tmp1 < tmp2) {
        l = mid + 1;
      } else {
        r = mid;
      }
    }
    ans.push_back(b[l]);
    st.erase(b[l]);
  }
  Answer(ans);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 256 KB # of queries: 2387
2 Correct 51 ms 256 KB # of queries: 2433
3 Correct 57 ms 384 KB # of queries: 2638
4 Correct 48 ms 256 KB # of queries: 2593
5 Correct 43 ms 384 KB # of queries: 2504
6 Correct 53 ms 384 KB # of queries: 2553
7 Correct 44 ms 384 KB # of queries: 2568
8 Correct 43 ms 384 KB # of queries: 2402
9 Correct 50 ms 384 KB # of queries: 2512
10 Correct 30 ms 256 KB # of queries: 1478
11 Correct 4 ms 256 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 1
13 Correct 5 ms 256 KB # of queries: 4
14 Correct 5 ms 384 KB # of queries: 7
15 Correct 5 ms 384 KB # of queries: 73
16 Correct 8 ms 256 KB # of queries: 187

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 256 KB # of queries: 2387
2 Correct 51 ms 256 KB # of queries: 2433
3 Correct 57 ms 384 KB # of queries: 2638
4 Correct 48 ms 256 KB # of queries: 2593
5 Correct 43 ms 384 KB # of queries: 2504
6 Correct 53 ms 384 KB # of queries: 2553
7 Correct 44 ms 384 KB # of queries: 2568
8 Correct 43 ms 384 KB # of queries: 2402
9 Correct 50 ms 384 KB # of queries: 2512
10 Correct 30 ms 256 KB # of queries: 1478
11 Correct 4 ms 256 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 1
13 Correct 5 ms 256 KB # of queries: 4
14 Correct 5 ms 384 KB # of queries: 7
15 Correct 5 ms 384 KB # of queries: 73
16 Correct 8 ms 256 KB # of queries: 187
17 Correct 538 ms 384 KB # of queries: 18008
18 Correct 448 ms 384 KB # of queries: 17231
19 Correct 536 ms 384 KB # of queries: 17451
20 Correct 430 ms 384 KB # of queries: 16277
21 Correct 372 ms 384 KB # of queries: 15362
22 Correct 494 ms 384 KB # of queries: 17617
23 Correct 470 ms 384 KB # of queries: 17170
24 Correct 197 ms 384 KB # of queries: 7885
25 Correct 452 ms 384 KB # of queries: 17118
26 Correct 420 ms 384 KB # of queries: 15989
27 Correct 186 ms 384 KB # of queries: 7994
28 Correct 482 ms 384 KB # of queries: 17935
29 Correct 447 ms 384 KB # of queries: 17915
30 Correct 525 ms 384 KB # of queries: 17935