oj.uz

Submission #166433

# Submission time Handle Problem Language Result Execution time Memory
166433 2019-12-02T12:18:42 Z dolphingarlic Library (JOI18_library) C++14
100 / 100
 583 ms 536 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

vector<int> known;

int getNext(int s, vector<int> &pnext) {
    vector<int> pnlist;
    int N = pnext.size();
    for (int i = 0; i < N; ++i) {
        if (pnext[i] == 1) pnlist.push_back(i);
    }
    if (pnlist.size() == 1) return pnlist[0];
    vector<int> pnfirst(N), pnsec(N);
    for (int i = 0; i < pnlist.size(); ++i) {
        if (i < pnlist.size() / 2)
            pnfirst[pnlist[i]] = 1;
        else
            pnsec[pnlist[i]] = 1;
    }
    int withoutStart = Query(pnfirst);
    pnfirst[s] = 1;
    if (withoutStart != Query(pnfirst)) {
        return getNext(s, pnsec);
    } else {
        pnfirst[s] = 0;
        return getNext(s, pnfirst);
    }
}

void Solve(int N) {
    if (N == 1) {
        Answer({1});
        return;
    }
    int start = -1;
    vector<int> toQuery(N, 1);
    for (int i = 0; i < N; ++i) {
        toQuery[i] = 0;
        if (Query(toQuery) == 1) {
            start = i;
            break;
        }
        toQuery[i] = 1;
    }
    vector<int> ans{start};
    for (int i = 1; i < N; ++i) {
        vector<int> probableNext(N, 1);
        for (int x : ans) probableNext[x] = 0;
        ans.push_back(getNext(ans.back(), probableNext));
    }
    vector<int> retVal;
    for (int x : ans) retVal.push_back(x + 1);
    Answer(retVal);
}

Compilation message

library.cpp: In function 'int getNext(int, std::vector<int>&)':
library.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < pnlist.size(); ++i) {
                     ~~^~~~~~~~~~~~~~~
library.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < pnlist.size() / 2)
             ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 248 KB # of queries: 2375
2 Correct 45 ms 376 KB # of queries: 2409
3 Correct 56 ms 376 KB # of queries: 2648
4 Correct 53 ms 376 KB # of queries: 2595
5 Correct 55 ms 248 KB # of queries: 2508
6 Correct 38 ms 328 KB # of queries: 2551
7 Correct 47 ms 424 KB # of queries: 2544
8 Correct 33 ms 404 KB # of queries: 2420
9 Correct 33 ms 396 KB # of queries: 2546
10 Correct 27 ms 376 KB # of queries: 1474
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 3 ms 248 KB # of queries: 1
13 Correct 2 ms 248 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 3 ms 248 KB # of queries: 77
16 Correct 5 ms 248 KB # of queries: 183

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 248 KB # of queries: 2375
2 Correct 45 ms 376 KB # of queries: 2409
3 Correct 56 ms 376 KB # of queries: 2648
4 Correct 53 ms 376 KB # of queries: 2595
5 Correct 55 ms 248 KB # of queries: 2508
6 Correct 38 ms 328 KB # of queries: 2551
7 Correct 47 ms 424 KB # of queries: 2544
8 Correct 33 ms 404 KB # of queries: 2420
9 Correct 33 ms 396 KB # of queries: 2546
10 Correct 27 ms 376 KB # of queries: 1474
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 3 ms 248 KB # of queries: 1
13 Correct 2 ms 248 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 3 ms 248 KB # of queries: 77
16 Correct 5 ms 248 KB # of queries: 183
17 Correct 583 ms 412 KB # of queries: 17982
18 Correct 546 ms 504 KB # of queries: 17293
19 Correct 527 ms 448 KB # of queries: 17467
20 Correct 504 ms 424 KB # of queries: 16325
21 Correct 460 ms 536 KB # of queries: 15324
22 Correct 581 ms 408 KB # of queries: 17669
23 Correct 519 ms 408 KB # of queries: 17224
24 Correct 164 ms 504 KB # of queries: 7915
25 Correct 561 ms 448 KB # of queries: 17136
26 Correct 474 ms 404 KB # of queries: 15963
27 Correct 193 ms 380 KB # of queries: 8040
28 Correct 470 ms 328 KB # of queries: 15957
29 Correct 493 ms 504 KB # of queries: 15939
30 Correct 495 ms 504 KB # of queries: 15957