oj.uz

Submission #508787

# Submission time Handle Problem Language Result Execution time Memory
508787 2022-01-13T18:50:43 Z kevinxiehk Library (JOI18_library) C++17
100 / 100
 313 ms 416 KB 
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

void Solve(int n) {
	vector<int> M(n);
    vector<int> res;
    if(n == 1) {
        res.pb(1);
        Answer(res);
        return;
    }
    vector<pair<int, int>> tmp;
	for(int i = 0; i < n; i++) {
		M[i] = 1;
        tmp.pb(mp(0, i));
	}
    for(int i = 0; i < n; i++) {
        M[i] = 0;
        int t = Query(M);
        M[i] = 1;
        if(t == 1) {
            res.pb(i);
            tmp[i].fi = 1;
            break;
        }
    }

    for(int lef = n - 1; lef >= 2; lef--) {
        sort(tmp.begin(), tmp.end());
        int hm = res[res.size() - 1];
        int l = 0, r = lef - 1;
        while(l < r) {
            int m = (l + r) / 2;
            for(int i = 0; i < n; i++) {
                M[i] = 0;
            }
            for(int i = l; i <= m; i++) {
                M[tmp[i].se] = 1;
            }
            int ee = Query(M);
            M[hm] = 1;
            int eee = Query(M);
            if(ee == eee) r = m;
            else l = m + 1;
        }
        res.pb(tmp[l].se);
        tmp[l].fi = 1;
    }

    sort(tmp.begin(), tmp.end());
    res.pb(tmp[0].se);

    for(auto &x: res) x++;
	Answer(res);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 200 KB # of queries: 2387
2 Correct 32 ms 200 KB # of queries: 2433
3 Correct 33 ms 200 KB # of queries: 2638
4 Correct 30 ms 200 KB # of queries: 2593
5 Correct 37 ms 200 KB # of queries: 2504
6 Correct 34 ms 200 KB # of queries: 2553
7 Correct 28 ms 200 KB # of queries: 2568
8 Correct 18 ms 200 KB # of queries: 2402
9 Correct 39 ms 200 KB # of queries: 2512
10 Correct 18 ms 200 KB # of queries: 1478
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 0 ms 200 KB # of queries: 4
14 Correct 0 ms 200 KB # of queries: 7
15 Correct 1 ms 200 KB # of queries: 73
16 Correct 2 ms 200 KB # of queries: 187

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 200 KB # of queries: 2387
2 Correct 32 ms 200 KB # of queries: 2433
3 Correct 33 ms 200 KB # of queries: 2638
4 Correct 30 ms 200 KB # of queries: 2593
5 Correct 37 ms 200 KB # of queries: 2504
6 Correct 34 ms 200 KB # of queries: 2553
7 Correct 28 ms 200 KB # of queries: 2568
8 Correct 18 ms 200 KB # of queries: 2402
9 Correct 39 ms 200 KB # of queries: 2512
10 Correct 18 ms 200 KB # of queries: 1478
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 0 ms 200 KB # of queries: 4
14 Correct 0 ms 200 KB # of queries: 7
15 Correct 1 ms 200 KB # of queries: 73
16 Correct 2 ms 200 KB # of queries: 187
17 Correct 297 ms 288 KB # of queries: 18008
18 Correct 304 ms 200 KB # of queries: 17231
19 Correct 313 ms 292 KB # of queries: 17451
20 Correct 239 ms 288 KB # of queries: 16277
21 Correct 245 ms 200 KB # of queries: 15362
22 Correct 298 ms 200 KB # of queries: 17617
23 Correct 183 ms 300 KB # of queries: 17170
24 Correct 133 ms 292 KB # of queries: 7885
25 Correct 267 ms 284 KB # of queries: 17118
26 Correct 250 ms 288 KB # of queries: 15989
27 Correct 80 ms 200 KB # of queries: 7994
28 Correct 286 ms 416 KB # of queries: 17935
29 Correct 303 ms 288 KB # of queries: 17915
30 Correct 288 ms 292 KB # of queries: 17935