oj.uz

Submission #172596

# Submission time Handle Problem Language Result Execution time Memory
172596 2020-01-02T07:31:58 Z ToMmyDong Library (JOI18_library) C++11
0 / 100
 579 ms 504 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);

    init();
    build();

	Answer(res);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 376 KB # of queries: 2542
2 Correct 33 ms 316 KB # of queries: 2531
3 Correct 50 ms 376 KB # of queries: 2716
4 Correct 36 ms 316 KB # of queries: 2678
5 Correct 53 ms 376 KB # of queries: 2684
6 Correct 53 ms 424 KB # of queries: 2684
7 Correct 50 ms 376 KB # of queries: 2676
8 Correct 47 ms 248 KB # of queries: 2565
9 Correct 47 ms 380 KB # of queries: 2659
10 Correct 29 ms 248 KB # of queries: 1559
11 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 2 ms 376 KB # of queries: 2
13 Correct 2 ms 252 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 6
15 Correct 3 ms 248 KB # of queries: 81
16 Correct 5 ms 248 KB # of queries: 195

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 376 KB # of queries: 2542
2 Correct 33 ms 316 KB # of queries: 2531
3 Correct 50 ms 376 KB # of queries: 2716
4 Correct 36 ms 316 KB # of queries: 2678
5 Correct 53 ms 376 KB # of queries: 2684
6 Correct 53 ms 424 KB # of queries: 2684
7 Correct 50 ms 376 KB # of queries: 2676
8 Correct 47 ms 248 KB # of queries: 2565
9 Correct 47 ms 380 KB # of queries: 2659
10 Correct 29 ms 248 KB # of queries: 1559
11 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 2 ms 376 KB # of queries: 2
13 Correct 2 ms 252 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 6
15 Correct 3 ms 248 KB # of queries: 81
16 Correct 5 ms 248 KB # of queries: 195
17 Correct 572 ms 376 KB # of queries: 18142
18 Correct 551 ms 376 KB # of queries: 17939
19 Correct 509 ms 328 KB # of queries: 18156
20 Correct 519 ms 248 KB # of queries: 16946
21 Correct 439 ms 248 KB # of queries: 15925
22 Correct 541 ms 428 KB # of queries: 18126
23 Correct 560 ms 376 KB # of queries: 18141
24 Correct 206 ms 376 KB # of queries: 8301
25 Correct 579 ms 376 KB # of queries: 17761
26 Correct 518 ms 380 KB # of queries: 16507
27 Correct 180 ms 248 KB # of queries: 8265
28 Correct 553 ms 320 KB # of queries: 16938
29 Correct 479 ms 376 KB # of queries: 16919
30 Correct 500 ms 408 KB # of queries: 16938