oj.uz

답안 #1080356

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1080356 2024-08-29T09:04:31 Z vjudge1 도서관 (JOI18_library) C++14
100 / 100
 358 ms 596 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

void Solve(int N)
{
	vector<int> M(N);
	vector<int> res(N);
	vector<int> rem(N);
	if(N <= 2){
        for(int i=0;i<N;i++) res[i] = i+1;
        Answer(res);
        return;
	}
	for(int i=0;i<N;i++) M[i] = 1;
    for(int i=0;i<N;i++){
        M[i] = 0;
        int A = Query(M);
        if(A == 1){
            res[0] = i+1;
            break;
        }
        M[i] = 1;
    }
    for(int i=0;i<N;i++) rem[i] = i+1;
    rem.erase(lower_bound(rem.begin(), rem.end(), res[0]));
    for(int i=1;i<N;i++){
        int L = 0, R = rem.size()-1;
        while(L <= R){
            int mid = (L + R) / 2;
            // cout << "!!! " << mid << '\n';
            for(int j=0;j<N;j++) M[j] = 0;
            for(int j=0;j<i;j++) M[res[j] - 1] = 1;
            for(int j=0;j<=mid;j++) M[rem[j] - 1] = 1;
            int v1 = Query(M);
            for(int j=0;j<i;j++) M[res[j] - 1] = 0;
            int v0 = Query(M);
            if(v0 == v1) R = mid-1;
            else L = mid+1;
        }
        // pos is L
        res[i] = rem[L];
        rem.erase(lower_bound(rem.begin(), rem.end(), res[i]));
    }
    Answer(res);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 344 KB # of queries: 2401
2 Correct 29 ms 344 KB # of queries: 2437
3 Correct 19 ms 344 KB # of queries: 2658
4 Correct 24 ms 344 KB # of queries: 2597
5 Correct 16 ms 344 KB # of queries: 2526
6 Correct 17 ms 344 KB # of queries: 2565
7 Correct 23 ms 344 KB # of queries: 2556
8 Correct 28 ms 344 KB # of queries: 2424
9 Correct 16 ms 344 KB # of queries: 2550
10 Correct 13 ms 344 KB # of queries: 1488
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 79
16 Correct 3 ms 344 KB # of queries: 195

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 344 KB # of queries: 2401
2 Correct 29 ms 344 KB # of queries: 2437
3 Correct 19 ms 344 KB # of queries: 2658
4 Correct 24 ms 344 KB # of queries: 2597
5 Correct 16 ms 344 KB # of queries: 2526
6 Correct 17 ms 344 KB # of queries: 2565
7 Correct 23 ms 344 KB # of queries: 2556
8 Correct 28 ms 344 KB # of queries: 2424
9 Correct 16 ms 344 KB # of queries: 2550
10 Correct 13 ms 344 KB # of queries: 1488
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 79
16 Correct 3 ms 344 KB # of queries: 195
17 Correct 358 ms 344 KB # of queries: 18030
18 Correct 328 ms 344 KB # of queries: 17279
19 Correct 331 ms 344 KB # of queries: 17479
20 Correct 327 ms 344 KB # of queries: 16301
21 Correct 257 ms 344 KB # of queries: 15352
22 Correct 318 ms 344 KB # of queries: 17663
23 Correct 318 ms 344 KB # of queries: 17250
24 Correct 106 ms 344 KB # of queries: 7917
25 Correct 323 ms 344 KB # of queries: 17158
26 Correct 299 ms 344 KB # of queries: 16003
27 Correct 106 ms 344 KB # of queries: 8046
28 Correct 294 ms 344 KB # of queries: 15975
29 Correct 325 ms 596 KB # of queries: 15957
30 Correct 290 ms 344 KB # of queries: 15975