Submission #490935

# Submission time Handle Problem Language Result Execution time Memory
490935 2021-11-29T22:18:01 Z ETK Library (JOI18_library) C++14
100 / 100
429 ms 580 KB
//GOODTEK!!!
#include "library.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n;
int ask(vi vec,int w=0){
    vi que(n);
    for(int x:vec)que[x-1]=1;
    if(w)que[w-1]=1;
    return Query(que);
}
void Solve(int N){
    n=N;
    vi p(n);
    for(int i=0;i<n;i++)p[i]=i+1;
    //random_shuffle(ALL(p));
    rep(i,1,n-1){
        swap(p[0],p[i]);
        if(i==n-1||ask(vi(p.begin()+1,p.end()))==1)break;
    }
    rep(i,0,n-2){
        auto l=p.begin()+i+1,r=p.end();
        while(l+1!=r){
            auto mid=l+(r-l)/2;
            if(ask(vi(l,mid))==ask(vi(l,mid),p[i]))r=mid;
            else l=mid;
        }
        swap(p[i+1],*l);
    }
    Answer(p);
}
# Verdict Execution time Memory Grader output
1 Correct 32 ms 200 KB # of queries: 2386
2 Correct 31 ms 200 KB # of queries: 2436
3 Correct 37 ms 200 KB # of queries: 2659
4 Correct 38 ms 200 KB # of queries: 2590
5 Correct 21 ms 296 KB # of queries: 2499
6 Correct 31 ms 296 KB # of queries: 2562
7 Correct 36 ms 300 KB # of queries: 2589
8 Correct 37 ms 200 KB # of queries: 2421
9 Correct 40 ms 292 KB # of queries: 2559
10 Correct 17 ms 200 KB # of queries: 1483
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 0
13 Correct 0 ms 200 KB # of queries: 3
14 Correct 0 ms 200 KB # of queries: 8
15 Correct 1 ms 200 KB # of queries: 79
16 Correct 3 ms 200 KB # of queries: 186
# Verdict Execution time Memory Grader output
1 Correct 32 ms 200 KB # of queries: 2386
2 Correct 31 ms 200 KB # of queries: 2436
3 Correct 37 ms 200 KB # of queries: 2659
4 Correct 38 ms 200 KB # of queries: 2590
5 Correct 21 ms 296 KB # of queries: 2499
6 Correct 31 ms 296 KB # of queries: 2562
7 Correct 36 ms 300 KB # of queries: 2589
8 Correct 37 ms 200 KB # of queries: 2421
9 Correct 40 ms 292 KB # of queries: 2559
10 Correct 17 ms 200 KB # of queries: 1483
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 0
13 Correct 0 ms 200 KB # of queries: 3
14 Correct 0 ms 200 KB # of queries: 8
15 Correct 1 ms 200 KB # of queries: 79
16 Correct 3 ms 200 KB # of queries: 186
17 Correct 429 ms 424 KB # of queries: 17989
18 Correct 396 ms 580 KB # of queries: 17210
19 Correct 365 ms 572 KB # of queries: 17490
20 Correct 374 ms 296 KB # of queries: 16298
21 Correct 321 ms 320 KB # of queries: 15313
22 Correct 412 ms 320 KB # of queries: 17632
23 Correct 380 ms 320 KB # of queries: 17181
24 Correct 129 ms 560 KB # of queries: 7842
25 Correct 368 ms 296 KB # of queries: 17123
26 Correct 383 ms 324 KB # of queries: 16000
27 Correct 125 ms 320 KB # of queries: 8019
28 Correct 385 ms 296 KB # of queries: 17578
29 Correct 419 ms 340 KB # of queries: 17529
30 Correct 370 ms 320 KB # of queries: 17578