oj.uz

답안 #341441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341441 2020-12-29T17:48:01 Z ijxjdjd 도서관 (JOI18_library) C++14
100 / 100
 371 ms 644 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;
#include <bits/stdc++.h>
vector<int> M;
int query(vector<int> q) {
    fill(M.begin(), M.end(), 0);
//    for (int i : q) {
//        cout << i << " ";
//    }
//    cout << '\n';
    for (int i : q) {
        M[i-1] = 1;
    }
    int res = Query(M);
//    cout << res << '\n';
    return res;
}
void Solve(int N)
{
    M.resize(N);
	vector<int> cur;
	vector<int> left(N);
	for(int i = 0; i < N; i++) {
		left[i] = i+1;
	}
	cur.push_back(*(left.end()-1));
	left.pop_back();
	while (left.size() > 0) {
        int low = 0;
        int high = left.size()-1;
        while (low < high) {
            int mid = (low + high)/2;
            vector<int> add(left.begin()+low, left.begin()+mid+1);
            int bef = query(add);
            add.insert(add.end(), cur.begin(), cur.end());
            int after = query(add);
            if (bef+1 == after) {
                low = mid+1;
            }
            else {
                high = mid;
            }
        }
        cout << '\n';
        vector<int> side = {cur[0], left[high]};
        if (query(side) == 1) {
            cur.insert(cur.begin(), left[high]);
        }
        else {
            cur.push_back(left[high]);
        }
        left.erase(left.begin() + high);
	}
	Answer(cur);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 364 KB # of queries: 2581
2 Correct 46 ms 364 KB # of queries: 2556
3 Correct 34 ms 508 KB # of queries: 2701
4 Correct 48 ms 364 KB # of queries: 2699
5 Correct 41 ms 364 KB # of queries: 2703
6 Correct 29 ms 404 KB # of queries: 2689
7 Correct 34 ms 408 KB # of queries: 2697
8 Correct 41 ms 492 KB # of queries: 2594
9 Correct 42 ms 364 KB # of queries: 2658
10 Correct 22 ms 364 KB # of queries: 1574
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 384 KB # of queries: 1
13 Correct 1 ms 364 KB # of queries: 4
14 Correct 1 ms 364 KB # of queries: 9
15 Correct 2 ms 364 KB # of queries: 88
16 Correct 4 ms 364 KB # of queries: 208

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 364 KB # of queries: 2581
2 Correct 46 ms 364 KB # of queries: 2556
3 Correct 34 ms 508 KB # of queries: 2701
4 Correct 48 ms 364 KB # of queries: 2699
5 Correct 41 ms 364 KB # of queries: 2703
6 Correct 29 ms 404 KB # of queries: 2689
7 Correct 34 ms 408 KB # of queries: 2697
8 Correct 41 ms 492 KB # of queries: 2594
9 Correct 42 ms 364 KB # of queries: 2658
10 Correct 22 ms 364 KB # of queries: 1574
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 384 KB # of queries: 1
13 Correct 1 ms 364 KB # of queries: 4
14 Correct 1 ms 364 KB # of queries: 9
15 Correct 2 ms 364 KB # of queries: 88
16 Correct 4 ms 364 KB # of queries: 208
17 Correct 334 ms 644 KB # of queries: 18151
18 Correct 323 ms 492 KB # of queries: 17898
19 Correct 371 ms 364 KB # of queries: 18163
20 Correct 322 ms 620 KB # of queries: 16961
21 Correct 308 ms 364 KB # of queries: 15920
22 Correct 359 ms 588 KB # of queries: 18135
23 Correct 357 ms 492 KB # of queries: 18084
24 Correct 122 ms 384 KB # of queries: 8298
25 Correct 364 ms 576 KB # of queries: 17724
26 Correct 334 ms 504 KB # of queries: 16540
27 Correct 146 ms 492 KB # of queries: 8290
28 Correct 335 ms 492 KB # of queries: 16955
29 Correct 295 ms 620 KB # of queries: 16936
30 Correct 338 ms 588 KB # of queries: 16955