oj.uz

Submission #347259

# Submission time Handle Problem Language Result Execution time Memory
347259 2021-01-12T12:46:48 Z jamezzz Library (JOI18_library) C++14
100 / 100
 342 ms 620 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#define fi first
#define se second
#define pb emplace_back
#define ll long long
#define INF 1023456789
#define INFll 1023456789123456789
#define all(x) x.begin(), x.end()
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;

int n;
vector<int> m, ans;
pbds s;

int qry(int l, int r){
    for (int i = l; i <= r; ++i){
        m[*s.find_by_order(i)] = 1;
    }
    int res = Query(m);
    for (int i = 0; i < n; ++i) m[i] = 0;
    return res;
}

void Solve(int N){
    if (N == 1){
        vector<int> v; v.pb(1);
        Answer(v); return;
    }
    n = N;
    m.resize(n, 1); int ept;
    for (int i = 0; i < n; ++i){
        m[i] = 0;
        if (Query(m) == 1){
            ept = i; break;
        }
        m[i] = 1;
    }
    ans.pb(ept + 1);
    for (int i = 0; i < n; ++i){
        m[i] = 0;
        if (ept != i) s.insert(i);
    }
    //printf("ept: %d\n", ept + 1);
    while (s.size()){
        int lo = 0, hi = s.size() - 1, mid, res;
        while (lo <= hi){
            mid = (lo + hi) / 2;
            m[ept] = 1;
            int t1 = qry(lo, mid);
            int t2 = qry(lo, mid);
            if (t1 == t2 + 1){
                lo = mid + 1;
            }
            else{
                hi = mid - 1;
                res = mid;
            }
        }
        ept = *s.find_by_order(res);
        s.erase(ept);
        ans.pb(ept + 1);
        //printf("ans: %d\n", ept + 1);
    }
    Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:43:25: warning: 'ept' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |     m.resize(n, 1); int ept;
      |                         ^~~
library.cpp:72:35: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |         ept = *s.find_by_order(res);
      |                                   ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 364 KB # of queries: 2401
2 Correct 31 ms 364 KB # of queries: 2437
3 Correct 43 ms 364 KB # of queries: 2658
4 Correct 29 ms 376 KB # of queries: 2597
5 Correct 35 ms 364 KB # of queries: 2526
6 Correct 36 ms 364 KB # of queries: 2565
7 Correct 37 ms 364 KB # of queries: 2556
8 Correct 35 ms 364 KB # of queries: 2424
9 Correct 36 ms 364 KB # of queries: 2550
10 Correct 26 ms 364 KB # of queries: 1488
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 3
13 Correct 1 ms 364 KB # of queries: 6
14 Correct 1 ms 364 KB # of queries: 9
15 Correct 2 ms 364 KB # of queries: 79
16 Correct 3 ms 364 KB # of queries: 195

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 364 KB # of queries: 2401
2 Correct 31 ms 364 KB # of queries: 2437
3 Correct 43 ms 364 KB # of queries: 2658
4 Correct 29 ms 376 KB # of queries: 2597
5 Correct 35 ms 364 KB # of queries: 2526
6 Correct 36 ms 364 KB # of queries: 2565
7 Correct 37 ms 364 KB # of queries: 2556
8 Correct 35 ms 364 KB # of queries: 2424
9 Correct 36 ms 364 KB # of queries: 2550
10 Correct 26 ms 364 KB # of queries: 1488
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 3
13 Correct 1 ms 364 KB # of queries: 6
14 Correct 1 ms 364 KB # of queries: 9
15 Correct 2 ms 364 KB # of queries: 79
16 Correct 3 ms 364 KB # of queries: 195
17 Correct 342 ms 620 KB # of queries: 18030
18 Correct 321 ms 380 KB # of queries: 17279
19 Correct 336 ms 448 KB # of queries: 17479
20 Correct 314 ms 492 KB # of queries: 16301
21 Correct 298 ms 492 KB # of queries: 15352
22 Correct 334 ms 508 KB # of queries: 17663
23 Correct 321 ms 492 KB # of queries: 17250
24 Correct 129 ms 364 KB # of queries: 7917
25 Correct 337 ms 492 KB # of queries: 17158
26 Correct 314 ms 364 KB # of queries: 16003
27 Correct 141 ms 412 KB # of queries: 8046
28 Correct 306 ms 364 KB # of queries: 15975
29 Correct 273 ms 380 KB # of queries: 15957
30 Correct 309 ms 364 KB # of queries: 15975