oj.uz

Submission #131201

# Submission time Handle Problem Language Result Execution time Memory
131201 2019-07-16T18:53:01 Z RezwanArefin01 Library (JOI18_library) C++17
100 / 100
 268 ms 504 KB 
#include <bits/stdc++.h>
#include "library.h"

using namespace std;

vector<vector<int>> comp; 
int N; 

vector<int> get(int l, int r) {
    vector<int> M(N, 0); 
    for(int i = l; i <= r; ++i) {
        for(int x : comp[i]) {
            M[x] = 1;
        }
    }
    return M; 
}


int find_comp(int u, int l, int r) {
    int lo = l, hi = r, ret;; 
    while(lo <= hi) {
        int mid = lo + hi >> 1; 

        vector<int> M = get(l, mid);  
        M[u] = 1; 

        if(Query(M) == mid - l + 1) {
            ret = mid; hi = mid - 1; 
        } else {
            lo = mid + 1;
        }
    }
    return ret; 
}

int find_side(int i, int c) {
    vector<int> M(N, 0); 
    M[i] = 1; 
    M[comp[c][0]] = 1; 

    if(Query(M) == 1) return 0; 
    else return 1; 
}

pair<int, int> find_merge(int u) {
    int lo = 0, hi = (int) comp.size() - 1;

    while(lo <= hi) {
        int mid = lo + hi >> 1; 

        vector<int> M = get(0, mid); 
        M[u] = 1; 

        int c = Query(M); 

        if(c == mid + 1) {
            return make_pair(find_comp(u, 0, mid), find_comp(u, mid + 1, (int) comp.size() - 1));
        } else if(c > mid + 1) {
            lo = mid + 1; 
        } else {
            hi = mid - 1;
        }
    }
    assert(0 == 1);
}

void Solve(int _N) {
    N = _N; 

    int C = 1;
    vector<int> M(N, 0); 
    M[0] = 1; 

    comp.push_back({0});

    for(int i = 1; i < N; ++i) {
        M[i] = 1; 
        int X = Query(M); 

        if(X > C) {
            comp.push_back({i}); 
        } else if(X == C) {
            int idx = find_comp(i, 0, (int) comp.size() - 1);
            int side = find_side(i, idx); 

            vector<int> &v = comp[idx]; 
            if(side) v.push_back(i); 
            else v.insert(v.begin(), i);  
        } else {
            int u, v; 
            tie(u, v) = find_merge(i);

            int su = find_side(i, u); 
            int sv = find_side(i, v); 

            if(su == 0) reverse(comp[u].begin(), comp[u].end());
            if(sv == 1) reverse(comp[v].begin(), comp[v].end()); 

            comp[u].push_back(i); 
            for(int x : comp[v]) {
                comp[u].push_back(x);
            }

            comp.erase(comp.begin() + v);
        } 

        C = X;
    }

    for(int &x : comp[0]) ++x; 
    Answer(comp[0]);
}

Compilation message

library.cpp: In function 'int find_comp(int, int, int)':
library.cpp:23:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
library.cpp: In function 'std::pair<int, int> find_merge(int)':
library.cpp:50:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
library.cpp: In function 'int find_comp(int, int, int)':
library.cpp:34:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ret; 
            ^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 248 KB # of queries: 1310
2 Correct 18 ms 312 KB # of queries: 1299
3 Correct 19 ms 312 KB # of queries: 1375
4 Correct 24 ms 248 KB # of queries: 1367
5 Correct 19 ms 316 KB # of queries: 1374
6 Correct 23 ms 376 KB # of queries: 1365
7 Correct 19 ms 320 KB # of queries: 1357
8 Correct 30 ms 248 KB # of queries: 1311
9 Correct 27 ms 376 KB # of queries: 1364
10 Correct 17 ms 376 KB # of queries: 815
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 3
13 Correct 2 ms 248 KB # of queries: 6
14 Correct 2 ms 248 KB # of queries: 10
15 Correct 3 ms 248 KB # of queries: 56
16 Correct 5 ms 248 KB # of queries: 120

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 248 KB # of queries: 1310
2 Correct 18 ms 312 KB # of queries: 1299
3 Correct 19 ms 312 KB # of queries: 1375
4 Correct 24 ms 248 KB # of queries: 1367
5 Correct 19 ms 316 KB # of queries: 1374
6 Correct 23 ms 376 KB # of queries: 1365
7 Correct 19 ms 320 KB # of queries: 1357
8 Correct 30 ms 248 KB # of queries: 1311
9 Correct 27 ms 376 KB # of queries: 1364
10 Correct 17 ms 376 KB # of queries: 815
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 3
13 Correct 2 ms 248 KB # of queries: 6
14 Correct 2 ms 248 KB # of queries: 10
15 Correct 3 ms 248 KB # of queries: 56
16 Correct 5 ms 248 KB # of queries: 120
17 Correct 223 ms 432 KB # of queries: 9022
18 Correct 254 ms 444 KB # of queries: 8964
19 Correct 260 ms 320 KB # of queries: 9019
20 Correct 240 ms 376 KB # of queries: 8500
21 Correct 179 ms 340 KB # of queries: 7942
22 Correct 268 ms 504 KB # of queries: 9064
23 Correct 260 ms 468 KB # of queries: 9022
24 Correct 101 ms 424 KB # of queries: 4148
25 Correct 214 ms 340 KB # of queries: 8873
26 Correct 242 ms 248 KB # of queries: 8267
27 Correct 94 ms 376 KB # of queries: 4109
28 Correct 89 ms 248 KB # of queries: 2997
29 Correct 97 ms 248 KB # of queries: 2994
30 Correct 87 ms 376 KB # of queries: 2997