oj.uz

Submission #172597

# Submission time Handle Problem Language Result Execution time Memory
172597 2020-01-02T07:36:02 Z ToMmyDong Library (JOI18_library) C++11
100 / 100
 652 ms 424 KB 
#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define SZ(i) int(i.size())

int n;

int vecQuery(const vector<int> &vec) {
	vector<int> M(n);
    for (auto el : vec) {
        M[el-1] = true;
    }
    return Query(M);
}

vector<int> res;

void init () {
    vector<int> M(n, 1);

    vector<int> ht;
    for (int i=0; i<n; i++) {
        M[i] = false;

        if (Query(M) == 1) {
            ht.emplace_back(i+1);
        }

        M[i] = true;
    }

    assert(ht.size() == 2);
    res[0] = ht[0];
    res[n-1] = ht[1];
}

void build () {
    set<int> left;
    REP1 (i, n) {
        left.insert(i);
    }
    left.erase(res[0]);
    left.erase(res[n-1]);

    for (int i=1; i<n-1; i++) {
        vector<int> cur;
        for (auto v : left) {
            cur.emplace_back(v);
        }

        while (SZ(cur) > 1) {
            vector<int> hf;
            vector<int> hs;
            REP (j, SZ(cur)) {
                if (j < SZ(cur)/2) {
                    hf.emplace_back(cur[j]);
                } else {
                    hs.emplace_back(cur[j]);
                }
            }

            int q1 = vecQuery(hf);
            hf.emplace_back(res[i-1]);
            if (q1 == vecQuery(hf)) {
                hf.pop_back();
                cur = hf;
            } else {
                cur = hs;
            }
        }

        res[i] = cur.front();
        left.erase(cur.front());
    }
}

void Solve(int N)
{
    n = N;
    res.resize(N);

    if (n == 1) {
        res[0] = 1;
    } else {
        init();
        build();
    }

	Answer(res);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 248 KB # of queries: 2542
2 Correct 49 ms 316 KB # of queries: 2531
3 Correct 48 ms 400 KB # of queries: 2716
4 Correct 53 ms 376 KB # of queries: 2678
5 Correct 42 ms 400 KB # of queries: 2684
6 Correct 56 ms 248 KB # of queries: 2684
7 Correct 58 ms 376 KB # of queries: 2676
8 Correct 34 ms 316 KB # of queries: 2565
9 Correct 46 ms 404 KB # of queries: 2659
10 Correct 29 ms 248 KB # of queries: 1559
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 296 KB # of queries: 2
13 Correct 2 ms 248 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 6
15 Correct 3 ms 248 KB # of queries: 81
16 Correct 4 ms 312 KB # of queries: 195

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 248 KB # of queries: 2542
2 Correct 49 ms 316 KB # of queries: 2531
3 Correct 48 ms 400 KB # of queries: 2716
4 Correct 53 ms 376 KB # of queries: 2678
5 Correct 42 ms 400 KB # of queries: 2684
6 Correct 56 ms 248 KB # of queries: 2684
7 Correct 58 ms 376 KB # of queries: 2676
8 Correct 34 ms 316 KB # of queries: 2565
9 Correct 46 ms 404 KB # of queries: 2659
10 Correct 29 ms 248 KB # of queries: 1559
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 296 KB # of queries: 2
13 Correct 2 ms 248 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 6
15 Correct 3 ms 248 KB # of queries: 81
16 Correct 4 ms 312 KB # of queries: 195
17 Correct 556 ms 324 KB # of queries: 18142
18 Correct 563 ms 376 KB # of queries: 17939
19 Correct 574 ms 376 KB # of queries: 18156
20 Correct 497 ms 376 KB # of queries: 16946
21 Correct 468 ms 376 KB # of queries: 15925
22 Correct 652 ms 320 KB # of queries: 18126
23 Correct 600 ms 424 KB # of queries: 18141
24 Correct 228 ms 376 KB # of queries: 8301
25 Correct 567 ms 412 KB # of queries: 17761
26 Correct 499 ms 376 KB # of queries: 16507
27 Correct 138 ms 380 KB # of queries: 8265
28 Correct 549 ms 324 KB # of queries: 16938
29 Correct 499 ms 408 KB # of queries: 16919
30 Correct 539 ms 376 KB # of queries: 16938