oj.uz

Submission #654400

# Submission time Handle Problem Language Result Execution time Memory
654400 2022-10-31T08:42:54 Z bachhoangxuan Library (JOI18_library) C++17
100 / 100
 339 ms 328 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

void Solve(int n)
{
    if(n==1){Answer({1});return;}
    vector<int> m(n),res(n);
    int st=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j==i) m[j]=0;
            else m[j]=1;
        }
        int d=Query(m);
        if(d==1) st=i;
    }
    res[0]=st+1;
    vector<int> p;
    for(int i=0;i<n;i++){
        if(i!=st) p.push_back(i);
    }
    for(int i=1;i<n;i++){
        int l=1,r=n-i,f=n-i;
        while(r>=l){
            int mid=(r+l)>>1;
            for(int j=0;j<n;j++) m[j]=0;
            for(int j=0;j<mid;j++) m[p[j]]=1;
            int a=Query(m);m[st]=1;
            int b=Query(m);
            if(a==b){f=mid;r=mid-1;}
            else l=mid+1;
        }
        res[i]=p[f-1]+1;st=p[f-1];
        p.erase(p.begin()+f-1);
    }
    Answer(res);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 208 KB # of queries: 2586
2 Correct 28 ms 208 KB # of queries: 2555
3 Correct 41 ms 304 KB # of queries: 2716
4 Correct 43 ms 208 KB # of queries: 2728
5 Correct 46 ms 208 KB # of queries: 2714
6 Correct 48 ms 208 KB # of queries: 2712
7 Correct 21 ms 296 KB # of queries: 2718
8 Correct 36 ms 208 KB # of queries: 2611
9 Correct 43 ms 208 KB # of queries: 2713
10 Correct 25 ms 208 KB # of queries: 1597
11 Correct 1 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 4
13 Correct 1 ms 208 KB # of queries: 7
14 Correct 1 ms 208 KB # of queries: 14
15 Correct 3 ms 208 KB # of queries: 99
16 Correct 3 ms 208 KB # of queries: 205

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 208 KB # of queries: 2586
2 Correct 28 ms 208 KB # of queries: 2555
3 Correct 41 ms 304 KB # of queries: 2716
4 Correct 43 ms 208 KB # of queries: 2728
5 Correct 46 ms 208 KB # of queries: 2714
6 Correct 48 ms 208 KB # of queries: 2712
7 Correct 21 ms 296 KB # of queries: 2718
8 Correct 36 ms 208 KB # of queries: 2611
9 Correct 43 ms 208 KB # of queries: 2713
10 Correct 25 ms 208 KB # of queries: 1597
11 Correct 1 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 4
13 Correct 1 ms 208 KB # of queries: 7
14 Correct 1 ms 208 KB # of queries: 14
15 Correct 3 ms 208 KB # of queries: 99
16 Correct 3 ms 208 KB # of queries: 205
17 Correct 279 ms 328 KB # of queries: 18160
18 Correct 224 ms 328 KB # of queries: 17933
19 Correct 282 ms 288 KB # of queries: 18178
20 Correct 308 ms 292 KB # of queries: 16960
21 Correct 268 ms 208 KB # of queries: 15937
22 Correct 296 ms 208 KB # of queries: 18168
23 Correct 307 ms 328 KB # of queries: 18157
24 Correct 135 ms 208 KB # of queries: 8321
25 Correct 287 ms 208 KB # of queries: 17675
26 Correct 275 ms 308 KB # of queries: 16597
27 Correct 100 ms 208 KB # of queries: 8287
28 Correct 288 ms 208 KB # of queries: 18954
29 Correct 264 ms 328 KB # of queries: 18933
30 Correct 339 ms 208 KB # of queries: 18954