oj.uz

Submission #566671

# Submission time Handle Problem Language Result Execution time Memory
566671 2022-05-22T15:16:00 Z two_sides Library (JOI18_library) C++17
100 / 100
 279 ms 336 KB 
#include <bits/stdc++.h>
#include "library.h"

namespace {
    using namespace std;
    
    const int N = 1005;

    bool vis[N];
}

void Solve(int n) {
    vector<int> ans;
    int lo = 2, hi = n;
    if (n == 1) {
        Answer(vector<int> (1, 1));
        return;
    }
    while (lo < hi) {
        int mi = (lo + hi) / 2;
        vector<int> bit(n);
        for (int i = 2; i <= mi; i++)
            bit[i - 1] = 1;
        int tmp = Query(bit); bit[0] = 1;
        if (Query(bit) > tmp) lo = mi + 1;
        else hi = mi;
    }
    ans.push_back(hi);
    ans.push_back(1);
    vis[1] = vis[hi] = 1;
    while (true) {
        vector<int> alive;
        for (int i = 1; i <= n; i++)
            if (!vis[i]) alive.push_back(i);
        lo = 0; hi = alive.size();
        while (lo < hi) {
            int mi = (lo + hi) / 2;
            vector<int> bit(n);
            for (int i = 0; i <= mi; i++)
                bit[alive[i] - 1] = 1;
            int tmp = Query(bit);
            bit[ans.back() - 1] = 1;
            if (Query(bit) > tmp) lo = mi + 1;
            else hi = mi;
        } 
        if (hi < alive.size()) {
            ans.push_back(alive[hi]);
            vis[alive[hi]] = 1;
        } else break;
    }
    reverse(ans.begin(), ans.end());
    while (true) {
        vector<int> alive;
        for (int i = 1; i <= n; i++)
            if (!vis[i]) alive.push_back(i);
        lo = 0; hi = alive.size();
        while (lo < hi) {
            int mi = (lo + hi) / 2;
            vector<int> bit(n);
            for (int i = 0; i <= mi; i++)
                bit[alive[i] - 1] = 1;
            int tmp = Query(bit);
            bit[ans.back() - 1] = 1;
            if (Query(bit) > tmp) lo = mi + 1;
            else hi = mi;
        } 
        if (hi < alive.size()) {
            ans.push_back(alive[hi]);
            vis[alive[hi]] = 1;
        } else break;
    }
    Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (hi < alive.size()) {
      |             ~~~^~~~~~~~~~~~~~
library.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         if (hi < alive.size()) {
      |             ~~~^~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 208 KB # of queries: 2412
2 Correct 37 ms 208 KB # of queries: 2372
3 Correct 32 ms 208 KB # of queries: 2526
4 Correct 32 ms 208 KB # of queries: 2556
5 Correct 28 ms 208 KB # of queries: 2550
6 Correct 32 ms 304 KB # of queries: 2540
7 Correct 35 ms 208 KB # of queries: 2526
8 Correct 29 ms 208 KB # of queries: 2430
9 Correct 30 ms 208 KB # of queries: 2508
10 Correct 23 ms 208 KB # of queries: 1468
11 Correct 1 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 1 ms 208 KB # of queries: 12
15 Correct 2 ms 208 KB # of queries: 90
16 Correct 3 ms 208 KB # of queries: 200

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 208 KB # of queries: 2412
2 Correct 37 ms 208 KB # of queries: 2372
3 Correct 32 ms 208 KB # of queries: 2526
4 Correct 32 ms 208 KB # of queries: 2556
5 Correct 28 ms 208 KB # of queries: 2550
6 Correct 32 ms 304 KB # of queries: 2540
7 Correct 35 ms 208 KB # of queries: 2526
8 Correct 29 ms 208 KB # of queries: 2430
9 Correct 30 ms 208 KB # of queries: 2508
10 Correct 23 ms 208 KB # of queries: 1468
11 Correct 1 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 1 ms 208 KB # of queries: 12
15 Correct 2 ms 208 KB # of queries: 90
16 Correct 3 ms 208 KB # of queries: 200
17 Correct 238 ms 296 KB # of queries: 17182
18 Correct 279 ms 292 KB # of queries: 17004
19 Correct 247 ms 208 KB # of queries: 17210
20 Correct 232 ms 296 KB # of queries: 16048
21 Correct 239 ms 336 KB # of queries: 15088
22 Correct 250 ms 208 KB # of queries: 17146
23 Correct 178 ms 296 KB # of queries: 17192
24 Correct 80 ms 292 KB # of queries: 7856
25 Correct 262 ms 292 KB # of queries: 16782
26 Correct 224 ms 296 KB # of queries: 15628
27 Correct 89 ms 300 KB # of queries: 7812
28 Correct 235 ms 288 KB # of queries: 17972
29 Correct 213 ms 208 KB # of queries: 17952
30 Correct 252 ms 292 KB # of queries: 17972