oj.uz

답안 #521516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521516 2022-02-02T10:11:57 Z cig32 도서관 (JOI18_library) C++17
100 / 100
 358 ms 300 KB 
#include "bits/stdc++.h"
using namespace std;
#include "library.h"
void Solve(int N)
{
  if(N == 1) {
    vector<int> res(1);
    res[0] = 1;
    Answer(res);
    return;
  }
  vector<int> M(N);
  for(int i=0; i<N; i++) M[i] = 1;
  vector<int> res(N);
  bool done[N];
  for(int i=0; i<N; i++) done[i] = 0;
  for(int i=0; i<N; i++) {
    M[i] = 0;
    int A = Query(M);
    if(A == 1) {
      res[0] = i + 1;
      done[i] = 1;
      break;
    }
    M[i] = 1;
  }
  for(int i=1; i<N; i++) {
    vector<int> v;
    for(int j=0; j<N; j++) {
      if(!done[j]) v.push_back(j);
    }
    int lb = 0, rb = v.size() - 1;
    while(lb < rb) {
      int mid = (lb + rb) >> 1;
      for(int j=0; j<N; j++) {
        if(done[j]) M[j] = 1;
        else M[j] = 0;
      }
      for(int j=0; j<=mid; j++) {
        M[v[j]] = 1;
      }
      int a1 = Query(M);
      for(int j=0; j<N; j++) {
        if(done[j]) M[j] = 0;
      }
      int a2 = Query(M);
      if(a1 == a2) rb = mid;
      else lb = mid + 1;
    }
    res[i] = v[lb] + 1;
    done[v[lb]] = 1;
  }
  Answer(res);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 296 KB # of queries: 2387
2 Correct 35 ms 292 KB # of queries: 2433
3 Correct 30 ms 288 KB # of queries: 2638
4 Correct 29 ms 200 KB # of queries: 2593
5 Correct 34 ms 220 KB # of queries: 2504
6 Correct 32 ms 200 KB # of queries: 2553
7 Correct 31 ms 200 KB # of queries: 2568
8 Correct 34 ms 200 KB # of queries: 2402
9 Correct 29 ms 200 KB # of queries: 2512
10 Correct 15 ms 296 KB # of queries: 1478
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 2 ms 200 KB # of queries: 73
16 Correct 3 ms 200 KB # of queries: 187

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 296 KB # of queries: 2387
2 Correct 35 ms 292 KB # of queries: 2433
3 Correct 30 ms 288 KB # of queries: 2638
4 Correct 29 ms 200 KB # of queries: 2593
5 Correct 34 ms 220 KB # of queries: 2504
6 Correct 32 ms 200 KB # of queries: 2553
7 Correct 31 ms 200 KB # of queries: 2568
8 Correct 34 ms 200 KB # of queries: 2402
9 Correct 29 ms 200 KB # of queries: 2512
10 Correct 15 ms 296 KB # of queries: 1478
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 2 ms 200 KB # of queries: 73
16 Correct 3 ms 200 KB # of queries: 187
17 Correct 358 ms 280 KB # of queries: 18008
18 Correct 237 ms 300 KB # of queries: 17231
19 Correct 292 ms 200 KB # of queries: 17451
20 Correct 290 ms 200 KB # of queries: 16277
21 Correct 270 ms 200 KB # of queries: 15362
22 Correct 306 ms 200 KB # of queries: 17617
23 Correct 344 ms 272 KB # of queries: 17170
24 Correct 123 ms 200 KB # of queries: 7885
25 Correct 282 ms 296 KB # of queries: 17118
26 Correct 283 ms 200 KB # of queries: 15989
27 Correct 123 ms 296 KB # of queries: 7994
28 Correct 262 ms 200 KB # of queries: 17935
29 Correct 227 ms 200 KB # of queries: 17915
30 Correct 286 ms 300 KB # of queries: 17935