oj.uz

Submission #136967

# Submission time Handle Problem Language Result Execution time Memory
136967 2019-07-26T17:40:24 Z Osama_Alkhodairy Library (JOI18_library) C++17
100 / 100
 518 ms 452 KB 
#include <bits/stdc++.h>
#include "library.h"
//~ #include "grader.cpp"
using namespace std;
 
void Solve(int N){
    if(N == 1){
        Answer({1});
        return;
    }
    int start = 0;
    vector <int> ans;
    while(start < N){
        vector <int> q(N, 1);
        q[start] = 0;
        if(Query(q) == 1){
            ans.push_back(start);
            break;
        }
        start++;
    }
    vector <int> all;
    for(int i = 0 ; i < N ; i++){
        if(i != ans.back()) all.push_back(i);
    }
    while(all.size()){
        int l = 0, r = (int)all.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            vector <int> q(N, 0);
            for(int i = 0 ; i <= mid ; i++){
                q[all[i]] = 1;
            }
            int x = Query(q);
            q[ans.back()] = 1;
            if(Query(q) == x) r = mid - 1;
            else l = mid + 1;
        }
        ans.push_back(all[l]);
        swap(all[l], all.back());
        all.pop_back();
    }
    for(auto &i : ans) i++;
    Answer(ans);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 248 KB # of queries: 2407
2 Correct 31 ms 316 KB # of queries: 2457
3 Correct 45 ms 252 KB # of queries: 2652
4 Correct 49 ms 248 KB # of queries: 2607
5 Correct 46 ms 380 KB # of queries: 2502
6 Correct 47 ms 316 KB # of queries: 2571
7 Correct 52 ms 248 KB # of queries: 2570
8 Correct 46 ms 296 KB # of queries: 2422
9 Correct 47 ms 248 KB # of queries: 2546
10 Correct 21 ms 376 KB # of queries: 1500
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 3
13 Correct 2 ms 376 KB # of queries: 6
14 Correct 2 ms 248 KB # of queries: 9
15 Correct 3 ms 248 KB # of queries: 81
16 Correct 6 ms 376 KB # of queries: 205

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 248 KB # of queries: 2407
2 Correct 31 ms 316 KB # of queries: 2457
3 Correct 45 ms 252 KB # of queries: 2652
4 Correct 49 ms 248 KB # of queries: 2607
5 Correct 46 ms 380 KB # of queries: 2502
6 Correct 47 ms 316 KB # of queries: 2571
7 Correct 52 ms 248 KB # of queries: 2570
8 Correct 46 ms 296 KB # of queries: 2422
9 Correct 47 ms 248 KB # of queries: 2546
10 Correct 21 ms 376 KB # of queries: 1500
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 3
13 Correct 2 ms 376 KB # of queries: 6
14 Correct 2 ms 248 KB # of queries: 9
15 Correct 3 ms 248 KB # of queries: 81
16 Correct 6 ms 376 KB # of queries: 205
17 Correct 518 ms 376 KB # of queries: 17994
18 Correct 507 ms 316 KB # of queries: 17215
19 Correct 497 ms 248 KB # of queries: 17545
20 Correct 476 ms 428 KB # of queries: 16317
21 Correct 376 ms 324 KB # of queries: 15330
22 Correct 484 ms 376 KB # of queries: 17669
23 Correct 456 ms 248 KB # of queries: 17224
24 Correct 172 ms 320 KB # of queries: 7923
25 Correct 490 ms 380 KB # of queries: 17106
26 Correct 397 ms 248 KB # of queries: 15995
27 Correct 173 ms 320 KB # of queries: 8020
28 Correct 485 ms 400 KB # of queries: 17547
29 Correct 440 ms 332 KB # of queries: 17557
30 Correct 478 ms 452 KB # of queries: 17547