oj.uz

Submission #133697

# Submission time Handle Problem Language Result Execution time Memory
133697 2019-07-21T08:42:07 Z doowey Library (JOI18_library) C++14
100 / 100
 551 ms 416 KB 
#include <bits/stdc++.h>
#include "library.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

int query(vector<int> t){
    bool yes = false;
    for(auto p : t) yes |= (p > 0);
    if(!yes) return 0;
    return Query(t);
}

int use[1005];

void Solve(int n){
    if(n==1){
        Answer({1});
        return;
    }
    if(n == 2){
        Answer({1,2});
        return;
    }
    for(int j = 0 ; j < n; j ++ ) use[j] = 0;
	vector<int> p(n);
    vector<int> answ;
    for(int i = 0 ; i < n; i ++ )
        p[i] = 1;
    int las;
    for(int i = 0 ; i < n; i ++ ){
        p[i]=0;
        if(query(p) == 1){
            answ.push_back(i);
            use[i] = 1;
            break;
        }
        p[i]=1;
    }
    int lf, rf, md;
    int cur, nx;
    vector<int> ni;
    for(int i = 1 ; i < n; i ++ ){
        las = answ.back();
        ni.clear();
        for(int j = 0 ; j < n; j ++ ){
            if(use[j] == 0){
                ni.push_back(j);
            }
        }
        lf = 0;
        rf = (int)ni.size() - 1;
        while(lf < rf){
            md = (lf + rf) / 2;
            for(int t = 0 ;t < n; t ++ )
                p[t] = 0;
            for(int t = 0 ; t <= md; t ++ )
                p[ni[t]] = 1;
            for(auto v : answ)
                p[v] = 0;
            cur = query(p);
            p[las] = 1;
            nx = query(p);
            if(cur == nx){
                rf = md;
            }
            else{
                lf = md + 1;
            }
        }
        answ.push_back(ni[rf]);
        use[ni[rf]] = 1;
    }
    for(int i = 0 ; i < n ; i ++ )
        answ[i] ++ ;
    Answer(answ);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 376 KB # of queries: 2387
2 Correct 38 ms 248 KB # of queries: 2433
3 Correct 49 ms 404 KB # of queries: 2638
4 Correct 52 ms 248 KB # of queries: 2593
5 Correct 33 ms 320 KB # of queries: 2504
6 Correct 52 ms 248 KB # of queries: 2553
7 Correct 36 ms 316 KB # of queries: 2568
8 Correct 47 ms 248 KB # of queries: 2402
9 Correct 40 ms 324 KB # of queries: 2512
10 Correct 27 ms 376 KB # of queries: 1478
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 380 KB # of queries: 0
13 Correct 2 ms 376 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 3 ms 248 KB # of queries: 73
16 Correct 5 ms 376 KB # of queries: 187

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 376 KB # of queries: 2387
2 Correct 38 ms 248 KB # of queries: 2433
3 Correct 49 ms 404 KB # of queries: 2638
4 Correct 52 ms 248 KB # of queries: 2593
5 Correct 33 ms 320 KB # of queries: 2504
6 Correct 52 ms 248 KB # of queries: 2553
7 Correct 36 ms 316 KB # of queries: 2568
8 Correct 47 ms 248 KB # of queries: 2402
9 Correct 40 ms 324 KB # of queries: 2512
10 Correct 27 ms 376 KB # of queries: 1478
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 380 KB # of queries: 0
13 Correct 2 ms 376 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 3 ms 248 KB # of queries: 73
16 Correct 5 ms 376 KB # of queries: 187
17 Correct 543 ms 416 KB # of queries: 18008
18 Correct 454 ms 376 KB # of queries: 17231
19 Correct 533 ms 248 KB # of queries: 17451
20 Correct 483 ms 332 KB # of queries: 16277
21 Correct 456 ms 408 KB # of queries: 15362
22 Correct 519 ms 252 KB # of queries: 17617
23 Correct 527 ms 408 KB # of queries: 17170
24 Correct 183 ms 376 KB # of queries: 7885
25 Correct 536 ms 328 KB # of queries: 17118
26 Correct 493 ms 328 KB # of queries: 15989
27 Correct 197 ms 248 KB # of queries: 7994
28 Correct 495 ms 248 KB # of queries: 17935
29 Correct 549 ms 248 KB # of queries: 17915
30 Correct 551 ms 248 KB # of queries: 17935