oj.uz

Submission #395745

# Submission time Handle Problem Language Result Execution time Memory
395745 2021-04-28T20:19:52 Z Victor Library (JOI18_library) C++17
100 / 100
 384 ms 700 KB 
#include "library.h"

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto& a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

vi dummy;
int book = 0;
uset<int> queried;

int binsearch(vi books) {
    vi qvec = dummy;
    qvec[book] = 1;

    if (sz(books) == 1) {
        qvec[books[0]] = 1;
        if (Query(qvec) != 1)
            return -1;
        else
            return books[0];
    }

    int take = sz(books) >> 1;

    rep(i, 0, take) qvec[books[i]] = 1;

    int moves = Query(qvec);
    qvec[book] = 0;
    vi nbooks;

    if (Query(qvec) < moves)
        rep(i, take, sz(books)) nbooks.push_back(books[i]);
    else
        rep(i, 0, take) nbooks.push_back(books[i]);

    return binsearch(nbooks);
}

void Solve(int n) {
    dummy.resize(n);

    vi ans(n);
    int rgt[n];
    memset(rgt, -1, sizeof(rgt));

    while (book != -1) {
        queried.insert(book);
        if(sz(queried)==n)break;

        vi vec;
        rep(i, 0, n) if (!queried.count(i)) vec.push_back(i);
        int next = binsearch(vec);

        rgt[book] = next;
        book = next;
    }

    book = 0;
    while (1) {
        queried.insert(book);
        if(sz(queried)==n)break;

        vi vec;
        rep(i, 0, n) if (!queried.count(i)) vec.push_back(i);
        int next = binsearch(vec);

        rgt[next] = book;
        book = next;
    }

    rep(i, 0, n) {
        ans[i] = book + 1;
        book = rgt[book];
    }
    
    Answer(ans);
}

Compilation message

library.cpp: In function 'int binsearch(vi)':
library.cpp:7:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for (int i = a; i < (b); ++i)
      |                                        ^
library.cpp:52:9: note: in expansion of macro 'rep'
   52 |         rep(i, take, sz(books)) nbooks.push_back(books[i]);
      |         ^~~
library.cpp: In function 'void Solve(int)':
library.cpp:68:23: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         if(sz(queried)==n)break;
      |                       ^
library.cpp:81:23: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |         if(sz(queried)==n)break;
      |                       ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB # of queries: 2586
2 Correct 38 ms 300 KB # of queries: 2591
3 Correct 50 ms 312 KB # of queries: 2726
4 Correct 50 ms 308 KB # of queries: 2724
5 Correct 45 ms 312 KB # of queries: 2708
6 Correct 47 ms 312 KB # of queries: 2714
7 Correct 39 ms 200 KB # of queries: 2716
8 Correct 46 ms 200 KB # of queries: 2611
9 Correct 48 ms 312 KB # of queries: 2709
10 Correct 27 ms 288 KB # of queries: 1601
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 5
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 2 ms 200 KB # of queries: 90
16 Correct 4 ms 200 KB # of queries: 213

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB # of queries: 2586
2 Correct 38 ms 300 KB # of queries: 2591
3 Correct 50 ms 312 KB # of queries: 2726
4 Correct 50 ms 308 KB # of queries: 2724
5 Correct 45 ms 312 KB # of queries: 2708
6 Correct 47 ms 312 KB # of queries: 2714
7 Correct 39 ms 200 KB # of queries: 2716
8 Correct 46 ms 200 KB # of queries: 2611
9 Correct 48 ms 312 KB # of queries: 2709
10 Correct 27 ms 288 KB # of queries: 1601
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 5
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 2 ms 200 KB # of queries: 90
16 Correct 4 ms 200 KB # of queries: 213
17 Correct 384 ms 480 KB # of queries: 18170
18 Correct 329 ms 400 KB # of queries: 17979
19 Correct 361 ms 480 KB # of queries: 18148
20 Correct 348 ms 392 KB # of queries: 16946
21 Correct 326 ms 328 KB # of queries: 15931
22 Correct 365 ms 396 KB # of queries: 18212
23 Correct 334 ms 492 KB # of queries: 18147
24 Correct 155 ms 700 KB # of queries: 8369
25 Correct 315 ms 392 KB # of queries: 17739
26 Correct 290 ms 348 KB # of queries: 16531
27 Correct 158 ms 576 KB # of queries: 8287
28 Correct 329 ms 504 KB # of queries: 16955
29 Correct 336 ms 364 KB # of queries: 16936
30 Correct 359 ms 396 KB # of queries: 16955