oj.uz

답안 #854157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854157 2023-09-26T09:26:05 Z NeroZein 도서관 (JOI18_library) C++17
100 / 100
 192 ms 1220 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

void Solve(int N) {
  if (N == 1) {
    Answer({1}); 
    return;
  }
  vector<int> M(N, 1);
  int st = 0; 
  vector<int> res;
  vector<int> in(N);
  for (int i = 0; i < N; ++i) {
    M[i] = 0; 
    if (Query(M) == 1) {
      res.push_back(i); 
      st = i;
      in[st] = 1; 
      break; 
    }
    M[i] = 1; 
  }
  auto make = [&](vector<int> v) {
    vector<int> ret(N);
    for (int i : v) {
      ret[i] = 1;
    }
    return ret;
  };
  for (int i = 1; i < N; ++i) {// == res.size() < n
    vector<int> available;
    for (int j = 0; j < N; ++j) {
      if (!in[j] && j != st) {
        available.push_back(j); 
      }
    }
    while (available.size() > 1) {
      vector<int> ask;
      for (int j = 0; j < (int) available.size() / 2; ++j) {
        ask.push_back(available[j]); 
      }
      int x = Query(make(ask));
      ask.push_back(st); 
      int y = Query(make(ask)); 
      ask.pop_back();
      if (x != y) {
        ask.clear();
        for (int j = (int) available.size() / 2; j < (int) available.size(); ++j) {
          ask.push_back(available[j]); 
        }
      } 
      available = ask; 
    }
    res.push_back(available[0]);
    in[res.back()] = true; 
    st = res.back(); 
  }
  for (int i = 0; i < N; ++i) {
    res[i]++; 
  }
  Answer(res);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 688 KB # of queries: 2375
2 Correct 17 ms 436 KB # of queries: 2409
3 Correct 22 ms 692 KB # of queries: 2648
4 Correct 19 ms 696 KB # of queries: 2595
5 Correct 24 ms 432 KB # of queries: 2508
6 Correct 16 ms 444 KB # of queries: 2551
7 Correct 22 ms 692 KB # of queries: 2544
8 Correct 22 ms 688 KB # of queries: 2420
9 Correct 17 ms 692 KB # of queries: 2546
10 Correct 11 ms 440 KB # of queries: 1474
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 0 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 77
16 Correct 2 ms 344 KB # of queries: 183

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 688 KB # of queries: 2375
2 Correct 17 ms 436 KB # of queries: 2409
3 Correct 22 ms 692 KB # of queries: 2648
4 Correct 19 ms 696 KB # of queries: 2595
5 Correct 24 ms 432 KB # of queries: 2508
6 Correct 16 ms 444 KB # of queries: 2551
7 Correct 22 ms 692 KB # of queries: 2544
8 Correct 22 ms 688 KB # of queries: 2420
9 Correct 17 ms 692 KB # of queries: 2546
10 Correct 11 ms 440 KB # of queries: 1474
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 0 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 77
16 Correct 2 ms 344 KB # of queries: 183
17 Correct 192 ms 1184 KB # of queries: 17982
18 Correct 173 ms 964 KB # of queries: 17293
19 Correct 181 ms 1220 KB # of queries: 17467
20 Correct 173 ms 932 KB # of queries: 16325
21 Correct 138 ms 976 KB # of queries: 15324
22 Correct 184 ms 700 KB # of queries: 17669
23 Correct 171 ms 968 KB # of queries: 17224
24 Correct 71 ms 696 KB # of queries: 7915
25 Correct 176 ms 704 KB # of queries: 17136
26 Correct 153 ms 968 KB # of queries: 15963
27 Correct 71 ms 952 KB # of queries: 8040
28 Correct 165 ms 692 KB # of queries: 15957
29 Correct 151 ms 704 KB # of queries: 15939
30 Correct 157 ms 712 KB # of queries: 15957